Source Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int OO = 1e9+7 ,N=2e5+5;

int dx[] = { 0, 0, 1, -1, 1, -1, 1, -1 }; // dir array
int dy[] = { 1, -1, 0, 0, 1, -1, -1, 1 };
void File(){
#ifndef ONLINE_JUDGE
    freopen("Input.txt", "r", stdin);
    freopen("Output.txt", "w", stdout);
#endif
}

int solve(){
    int n;cin>>n;
    vector<int>a(n+1),ans(n+1);
    vector<pair<int,int>>p(n+1),p2(n+1);
    set<pair<int,int>>st;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        st.insert({a[i]-i,i});
    }
    for(int i=1;i<=n && !st.empty();i++){
        int x= -(a[i]+i);
        auto lb= st.lower_bound({x,0});
        if(lb!=st.end()){
            vector<pair<int,int>>v;
            while(lb!=st.end()&& lb->first >=x){
                v.push_back(*lb);
                lb++;
            }
            for(auto j:v){
                ans[j.second]=i;
                st.erase(j);
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<' ';
    }
    cout<<'\n';
    return 0;
}
int main() {
    File();
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t,i=1;cin>>t;
    while(t--)
        solve();

}
//Solve on paper first
//Overflooooooow
//Reverse Thinking
//If there's an equation, transform it into an easy one
//READ ALL PROBLEMS
//Verify Your thought before Coding
Copy
Easy challenge? ahmes
GNU G++17
51 ms
500 KB
Wrong Answer