Cod sursa(job #2461425)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 25 septembrie 2019 17:57:16
Problema Schi Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <bits/stdc++.h>

FILE *in = fopen("schi.in", "r"), *out = fopen("schi.out", "w") ;

const int MV = 3e4 ;

int n ;
int v[MV + 5] ;
int aib[MV + 5] ;
int ans[MV + 5] ;

void update(int poz, int val) {
        for ( ; poz <= n ; poz += (poz & - poz)) {
                aib[poz] += val ;
        }
}

int querry(int poz) {
        int ret(0) ;
        for ( ; poz > 0 ; poz -= (poz & - poz)) {
                ret += aib[poz] ;
        }
        return ret ;
}

int Binary_search(int val) {
        int ret(0) ;
        for (int step(1 << 18) ; step ; step >>= 1) {
                if (ret + step <= n and ret + step - querry(ret + step) < val) {
                        ret |= step ;
                }
        }
        return ret + 1 ;
}

void adauga(int val, int player) {
        int poz = Binary_search(val) ;
        ans[poz] = player ;
        update(poz, 1) ;
}

int main() {
        fscanf(in, "%d", &n) ;
        for (int i = 1 ; i <= n ; ++ i) {
                fscanf(in, "%d", v + i) ;
        }
        for (int i = n ; i > 0 ; -- i) {
                adauga(v[i], i) ;
        }
        for (int i = 1 ; i <= n ; ++ i) {
                fprintf(out, "%d\n", ans[i]) ;
        }
}