CSES - Reversal Sorting | Sắp xếp ngược

Xem PDF
Tác giả:
Flower_On_Stone , unglinh , SPyofgame , ngpin_04
Dạng bài
Điểm: 2200 Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình
  • Cho một mảng chứa một hoán vị của các số nguyên \(1,2,...,n\). Hãy sắp xếp mảng theo thứ tự tăng dần bằng cách đảo ngược các mảng con. Bạn có thể in ra bất kỳ lời giải nào có nhiều nhất \(n\) lần đảo.

Input

  • Dòng đầu tiên nhập số nguyên \(n\): kích thước của mảng. Các phần tử của mảng được đánh số \(1,2,…, n\).
  • Dòng tiếp theo có n số nguyên \(x_1, x_2,…, x_n\): phần tử của mảng

Output

  • Dòng đầu in số nguyên \(k\): số lần đảo.
  • \(k\) dòng tiếp theo mô tả cho mỗi lần đảo. Mỗi dòng có hai số nguyên \(a\) và \(b\): đảo ngược mảng con từ \(a\) đến \(b\).

Constraints

  • \(1\leq n \leq 2 ⋅ 10^5\)

Example

Sample input:

4  
2 3 1 4

Sample output:

2  
1 3  
2 3

Bình luận


  • 0
    vanphukhang_0604    8:31 p.m. 14 Tháng 8, 2023 ← chỉnh sửa 5

    CSES - Reversal Sorting | Sắp xếp ngược

    Cho một mảng chứa một hoán vị của các số nguyên \(1, 2, \ldots, n\). Nhiệm vụ của bạn là sắp xếp mảng này bằng cách đảo ngược các mảng con của nó. Bạn có thể trả lời bằng bất kì cách làm nào có tối đa \(n\) lần đảo ngược.

    Input

    • Dòng đầu tiên chứa số nguyên \(n \ (1 \leq n \leq 2 \cdot 10^5)\): kích thước của mảng. Các phần tử của mảng được đánh số \(1, 2, \ldots, n\).
    • Dòng tiếp theo chứa \(n\) số nguyên \(x_1, x_2, \ldots, x_n\): các phần tử của mảng.

    Output

    • Dòng đầu in ra số nguyên \(k \ -\) số lần đảo.
    • \(k\) dòng tiếp theo mô tả cho mỗi lần đảo. Mỗi dòng in ra hai số nguyên \(a\) và \(b\), ứng với thao tác đảo ngược mảng con từ vị trí \(a\) đến vị trí \(b\).

    Example

    Test 1

    Input 
    4
2 3 1 4
    Output 
    2  
1 3
2 3

    • 1
      nullType    8:15 a.m. 20 Tháng 12, 2022

      My solution passes the original problem on the CSES site, however, it WAs here.

      Bạn có thể in ra bất kỳ lời giải nào có nhiều nhất \(n\) lần đảo.

      Despite the above sentence from the problem statement, it seems the judge only checks the output to see if it is identical to the model output.