Cod sursa(job #2019641)

Utilizator alexsandulescuSandulescu Alexandru alexsandulescu Data 8 septembrie 2017 11:13:17
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
#include <climits>
#define ub(x) (x&(-x))
using namespace std;

ifstream f("schi.in");
ofstream g("schi.out");

int N, AIB[30003], a[30003], sol[30003];
void add(int poz, int val) {
    for(int i = poz; i <= N; i += ub(i)) AIB[i] += val;
}
int sum(int poz) {
    int s = 0;
    for(int i = poz; i > 0; i -= ub(i))
        s += AIB[i];
    return s;
}
int cautbin(int x) {
    int st = 1, dr = N, ans = INT_MAX, mij = 0;
    while(st <= dr) {
        mij = (st + dr) / 2;
        int nr = sum(mij);
        if(nr == x && mij < ans) {
            ans = mij;
        }
        else if(nr < x) st = mij + 1;
        else            dr = mij - 1;
    }
    return ans;
}
int main()
{
    f >> N;
    for(int i = 1; i <= N; i++)
        AIB[i] = ub(i), f >> a[i];
    for(int i = N; i >= 1; i--) {
        int poz = cautbin(a[i]);
        add(poz, -1);
        sol[poz] = i;
    }
    for(int i = 1; i <= N; i++)
        g << sol[i] << "\n";
    return 0;
}