Cod sursa(job #1469274)

Utilizator MaligMamaliga cu smantana Malig Data 7 august 2015 21:30:26
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>
#include<queue>

#define ull unsigned long long
#define ll long long
#define pb push_back
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)

using namespace std;
int N;
short v[30010],aib[30010],rez[30010];

void Update(int,int);
int Query(int);
int Search(int);

int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    scanf("%i",&N);
    FOR (i,1,N) {
        scanf("%i",&v[i]);
        Update(i,1);
    }
    ROF (i,N,1) {
        int val=Search(v[i]);
        rez[val]=i;
        Update(val,-1);
    }
    FOR (i,1,N) {
        printf("%i\n",rez[i]);
    }
    fclose(stdin);fclose(stdout);
    return 0;
}

void Update(int poz,int val) {
    int C=0;
    while (poz<=N) {
        aib[poz]+=val;
        while (!(poz&(1<<C))) {
            ++C;
        }
        poz+=(1<<C);
        ++C;
    }
}

int Query(int poz) {
    int S=0,C=0;
    while (poz) {
        S+=aib[poz];
        while (!(poz&(1<<C))) {
            ++C;
        }
        poz-=(1<<C);
        ++C;
    }
    return S;
}

int Search(int poz) {
    int left,right;
    left=1;
    right=N;
    while (left<right) {
        int mij=(left+right)>>1;
        int valstanga=Query(mij);
        if (valstanga>=poz) {
            right=mij;
        }
        else {
            left=mij+1;
        }
    }
    return left;
}