Codeforces Round 914 (Div. 2) 1904B. Collecting Game Solution

 Problem Link:  https://codeforces.com/problemset/problem/1904/B

Solution in C++:

1. /// Author : AH_Tonmoy
2. #include <bits/stdc++.h>
3. using namespace std;
4. int32_t main() {
5. ios_base::sync_with_stdio(0);
6. cin.tie(0);
7. int t;
8. cin >> t;
9. while (t--) {
10. int n ; cin >> n ;
11. vector<pair<int,int>>a(n) ;
12. for ( int i = 0 ; i < n ; i++){
13. cin >> a[i].first ;
14. a[i].second = i ;
15. }
16. sort(a.begin(),a.end()) ;
17. vector<long long > p(n,0) ;
18. p[0] = a[0].first ;
19. for ( int i = 1 ; i < n ; i++){
20. p[i] = p[i - 1 ] + a[i].first ;
21. }
22. stack<int> st ;
23. vector<int>ans(n) ;
24. for ( int i = 0 ; i < n ; i++){
25. st.push(a[i].second) ;
26. if( p[i] < a[i+1].first or i == n - 1 ){
27. while(!st.empty()){
28. ans[st.top()] = i ;
29. st.pop() ;
30. }
31. }
32. }
33. for ( auto i : ans ){
34. cout << i <<" ";
35. }
36. cout <<'\n';
37. }
38. return 0 ;
39. }