fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4.  
  5. int main() {
  6. 	ll t;
  7. 	cin >> t;
  8. 	while (t--) {
  9. 		ll n;
  10. 		cin >> n;
  11. 		vector<pair<ll, ll>> v(n);
  12. 		for (ll i = 0; i < n; i++) {
  13. 			cin >> v[i].first;
  14. 			v[i].second = i;
  15. 		}
  16. 		if (v.size() == 1) {
  17. 			cout << "0\n";
  18. 			continue;
  19. 		}
  20. 		sort(v.begin(), v.end());
  21. 		vector<ll> psum(n);
  22. 		psum[0] = v[0].first;
  23. 		for (ll i = 1; i < n; i++) {
  24. 			psum[i] = psum[i - 1] + v[i].first;
  25. 		}
  26. 		vector<ll> a1(n);
  27. 		for (ll i = 0; i < n; i++) a1[i] = i;
  28. 		vector<ll> mf(n - 1);
  29. 		if (psum[0] >= v[1].first) mf[0] = 1;
  30. 		else mf[0] = 0;
  31. 		for (ll i = 1; i < n - 1; i++) {
  32. 			if (psum[i] >= v[i + 1].first) mf[i] = mf[i - 1] + 1;
  33. 			else mf[i] = 0;
  34. 		}
  35. 		for (ll i = 0; i < n - 1; i++) {
  36. 			a1[i] += mf[i];
  37. 		}
  38. 		vector<ll> af(n);
  39. 		for (ll i = 0; i < n; i++) {
  40. 			af[v[i].second] = a1[i];
  41. 		}
  42. 		for (ll i = 0; i < n-1; i++) cout << mf[i] << " ";
  43. 		cout << "\n";
  44. 	}
  45. }
  46.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
4
5
20 5 1 4 2
3
1434 7 1442
1
1
5
999999999 999999999 999999999 1000000000 1000000000
stdout
copy 
0 0 1 0 
0 0 
0
1 2 3 4
https://ideone.com/ZHlBR5
language:
C++ (gcc 8.3)
created:
4 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!