Cod sursa(job #2869988)

Utilizator BorodiBorodi Bogdan Borodi Data 11 martie 2022 23:17:16
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <string>
#include <cstring>
#include <map>
#include <algorithm>
#include <vector>
#include <queue>
#define MOD 32173
#define Nmax 30001
using namespace std;

ifstream fin("schi.in");
ofstream fout("schi.out");

const int oo = 1 << 28;
typedef vector < int > VI;

int V[Nmax], aib[Nmax], sol[Nmax];
int n;

void update(int pos, int x){
    for(int i = pos; i < Nmax; i += i & -i)
        aib[i] += x;
}
int query(int pos){
    int sum = 0;

    for(int i = pos; i > 0; i -= i & -i)
        sum += aib[i];

    return sum;
}
int Binary_Search(int st, int dr, int caut){
    int ans = 0;

    while(st <= dr){
        int mid = (st + dr) / 2;
        int x = query(mid);

        if(x >= caut)
            dr = mid - 1,
            ans = mid;
        else st = mid + 1;
    }
    return ans;
}
int main() {
    fin >> n;

    for(int i = 1; i <= n; ++i){
        fin >> V[i];
        update(i, 1);
    }
    
    for(int i = n; i > 0; --i){
        int pos = Binary_Search(1, n, V[i]);
        update(pos, -1);
        sol[pos] = i;
    }   

    for(int i = 1; i <= n; ++i)
        fout << sol[i] << '\n';

    return 0;
}