Cod sursa(job #2461429)

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

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

const int MV = 3e4 ;
const int SIZE = 1 << 12 ;

int n ;
int v[MV + 5] ;
int aib[MV + 5] ;
int ans[MV + 5] ;
char Buffer[SIZE], ch ;
int point(SIZE) ;

void advance() {
        if (point == SIZE) {
                fread(Buffer, 1, SIZE, in) ;
                point = 0 ;
        }
        ch = Buffer[point ++] ;
}

int read() {
        int ret(0) ;
        while (!isdigit(ch)) {
                advance() ;
        }
        while (isdigit(ch)) {
                ret = ret * 10 + (ch - '0') ;
                advance() ;
        }
        return ret ;
}

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() {
        n = read() ;
        for (int i = 1 ; i <= n ; ++ i) {
                v[i] = read() ;
        }
        for (int i = n ; i > 0 ; -- i) {
                adauga(v[i], i) ;
        }
        for (int i = 1 ; i <= n ; ++ i) {
                fprintf(out, "%d\n", ans[i]) ;
        }
}