trang chủ / đề bài / icpc26_mn_c

Sắp xếp Sodium

Đề bài

Mô tả

Sodium đã cài đặt phiên bản thuật toán Quicksort của riêng mình, gọi là Sodium Sort, để sắp xếp một mảng a có độ dài n. Để chọn chốt (pivot) cho bước phân hoạch, cậu dùng một dãy số nguyên R được sinh sẵn từ trước.

Sodium Sort được cài đặt theo mã giả sau:

int it = 1;
long long tot_length = 0;

void sodium_sort(int l, int r) {
    if (l > r) return;
    tot_length += r - l + 1;
    int pivot_index = l + (R[it] % (r - l + 1));
    it++;
    int p = partition(l, r, pivot_index);
    sodium_sort(l, p - 1);
    sodium_sort(p + 1, r);
}

Có thể thấy biến toàn cục tot_length đóng vai trò một thước đo chi phí, bằng tổng độ dài của mọi đoạn con được xử lý trong quá trình sắp xếp. Ngoài ra, bộ đếm toàn cục it được tăng đúng n lần khi sắp xếp một mảng có kích thước n.

Khi partition(l, r, pivot_index) được gọi trên một đoạn con, nó dùng phần tử tại chỉ số pivot_index làm giá trị chốt x và sắp xếp lại đoạn con a[l…r] sao cho:

  • Mọi phần tử nhỏ hơn x được chuyển sang bên trái chốt.
  • Mọi phần tử lớn hơn x được chuyển sang bên phải chốt.
  • Các phần tử được đặt vào đoạn con bên trái và đoạn con bên phải giữ nguyên thứ tự tương đối của chúng ngay trước lần gọi hiện tại. Ví dụ: khi gọi partition(1, 5, 5) trên [1,5,2,4,3] (giá trị chốt là x=3), mảng cuối cùng trở thành [1,2,3,5,4].
  • Hàm trả về chỉ số mới p là vị trí cuối cùng của chốt x.

Ban đầu Sodium gọi sodium_sort(1, n) để sắp xếp mảng. Sodium Sort luôn sắp xếp mảng đúng, nhưng thời gian chạy phụ thuộc vào thứ tự ban đầu của các phần tử. Bạn của Sodium là Sulfur muốn "hack" Sodium Sort bằng cách tìm một dữ liệu vào khiến nó chạy chậm nhất có thể.

Nhiệm vụ của bạn là giúp Sulfur. Cho độ dài mảng n và dãy R, hãy dựng một hoán vị của các số nguyên từ 1 đến n làm mảng a sao cho giá trị cuối cùng của bộ đếm toàn cục tot_length là lớn nhất.

Dữ liệu vào

  • Dòng đầu tiên chứa một số nguyên n (1≤n≤2·105): kích thước của mảng cần sắp xếp.
  • Dòng thứ hai chứa n số nguyên R1,R2,…,Rn (0≤Ri≤109): các phần tử của dãy sinh sẵn dùng để chọn chốt của Sodium.

Dữ liệu ra

In ra một dòng gồm n số nguyên, là một hoán vị của 1,2,…,n làm cho giá trị cuối cùng của bộ đếm tot_length lớn nhất sau khi mảng được sắp xếp xong. (Một hoán vị độ dài n là một mảng chứa mỗi số nguyên từ 1 đến n đúng một lần.) Nếu có nhiều hoán vị thỏa mãn, bạn có thể in ra hoán vị bất kỳ.

Ràng buộc

  • 1≤n≤2·105.
  • 0≤Ri≤109.

Ví dụ

Input Output Giải thích
3
5 2 9
2 3 1 Lần gọi sodium_sort(1, 3) cộng 3, chốt ở chỉ số 1+5mod3=3 có giá trị 1, mảng thành [1,2,3]. Lần gọi sodium_sort(2, 3) cộng 2, chốt ở chỉ số 2+2mod2=2 có giá trị 2. Lần gọi sodium_sort(3, 3) cộng 1. Tổng tot_length =6, lớn nhất có thể.
5
4 0 7 1 3
2 5 3 4 1 Ví dụ bổ sung (không có trong đề gốc). Các chốt lần lượt ở chỉ số 5,2,4,5,5 với giá trị 1,2,3,4,5; mảng sau lần phân hoạch đầu tiên là [1,2,5,3,4], sau lần thứ ba là [1,2,3,5,4]. Tổng tot_length =5+4+3+2+1=15.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0