fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4.  
  5. void solve() {
  6.     int n;
  7.     cin >> n;
  8.     vector<int> k(n);
  9.     vector<pair<int, int>> ans(n);
  10.  
  11.     for (int i = 0; i < n; i++) {
  12.         int p;
  13.         cin >> p;
  14.         ans[i] = {p, i};
  15.     }
  16.  
  17.     sort(ans.begin(), ans.end(), greater<pair<int, int>>());
  18.  
  19.     vector<int> p_sum(n + 1, 0);
  20.     p_sum[n - 1] = ans[n - 1].first;
  21.  
  22.     for (int i = n - 2; i >= 0; i--) {
  23.         p_sum[i] = p_sum[i + 1] + ans[i].first;
  24.     }
  25.  
  26.     vector<int> s;
  27.     for (int i = 0; i < n; i++) {
  28.         int f = p_sum[i + 1] + ans[i].first;
  29.         int id = 0;
  30.         int h = f;
  31.         auto it = upper_bound(s.begin(), s.end(), h);
  32.         id = distance(s.begin(), it);
  33.  
  34.         k[ans[i].second] = (n - i - 1) + id;
  35.         s.insert(upper_bound(s.begin(), s.end(), ans[i].first), ans[i].first);
  36.     }
  37.  
  38.     for (int i = 0; i < n; i++) {
  39.         cout << k[i] << " ";
  40.     }
  41.     cout << endl;
  42. }
  43.  
  44. signed main() {
  45.  
  46.     int t;
  47.     cin >> t;
  48.     while (t--) {
  49.         solve();
  50.     }
  51.     return 0;
  52. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
4
5
20 5 1 4 2
3
1434 7 1442
1
1
5
999999999 999999999 999999999 1000000000 1000000000
stdout
copy 
4 3 0 3 1 
1 0 2 
0 
2 4 4 4 4
https://ideone.com/mtQOnh
language:
C++ (gcc 8.3)
created:
6 days 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!