fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <numeric>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. void solve() {
  9.     int n;
  10.     cin >> n;
  11.  
  12.     // Khởi tạo mảng kích thước n + 1 để sử dụng index từ 1 đến n
  13.     vector<long long> a(n + 1);
  14.     for (int i = 1; i <= n; ++i) {
  15.         cin >> a[i];
  16.     }
  17.  
  18.     // Mảng S lưu tổng hậu tố, kích thước n + 1
  19.     vector<long long> S(n + 1, 0);
  20.  
  21.     // S_n = 0 theo đúng công thức phân tích
  22.     S[n] = 0;
  23.  
  24.     // Tính tổng hậu tố S_i = a_i + a_{i+1} + ... + a_{n-1}
  25.     for (int i = n - 1; i >= 1; --i) {
  26.         S[i] = S[i + 1] + a[i];
  27.     }
  28.  
  29.     // Lưu trữ các cặp {Giá trị tổng hậu tố, Vị trí ban đầu}
  30.     vector<pair<long long, int>> S_vals(n + 1);
  31.     for (int i = 1; i <= n; ++i) {
  32.         S_vals[i] = {S[i], i};
  33.     }
  34.  
  35.     // Sắp xếp các giá trị từ index 1 đến n tăng dần
  36.     sort(S_vals.begin() + 1, S_vals.end());
  37.  
  38.     // Khôi phục hoán vị p kích thước n + 1
  39.     vector<int> p(n + 1);
  40.     for (int i = 1; i <= n; ++i) {
  41.         // Gán giá trị i cho phần tử có tổng hậu tố nhỏ thứ i
  42.         p[S_vals[i].second] = i; 
  43.     }
  44.  
  45.     // In kết quả từ phần tử 1 đến n
  46.     for (int i = 1; i <= n; ++i) {
  47.         cout << p[i] << (i == n ? "" : " ");
  48.     }
  49.     cout << "\n";
  50. }
  51.  
  52. int main() {
  53.     // Tối ưu hóa I/O cho luồng dữ liệu lớn
  54.     ios_base::sync_with_stdio(false);
  55.     cin.tie(NULL);
  56.  
  57.     int t;
  58.     if (cin >> t) {
  59.         while (t--) {
  60.             solve();
  61.         }
  62.     }
  63.     return 0;
  64. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
7
1
0
2
1000000000 -1000000000
3
1 2 3
4
-1 -2 -3 -4
5
-1 2 -3 2 -1
6
1 -1 3 -4 1 -3
7
-3 -2 -1 4 -1 -2 -3
stdout
copy 
1
2 1
3 2 1
1 2 3 4
2 4 1 5 3
3 2 4 1 6 5
1 3 5 7 2 4 6
https://ideone.com/xH40wA
language:
C++14 (gcc 8.3)
created:
5 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!