Cod sursa(job #1469269)

Utilizator MaligMamaliga cu smantana Malig Data 7 august 2015 21:18:03
Problema Schi Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 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()
{
    FILE *f,*g;
    f=fopen("schi.in","r");
    g=fopen("schi.out","w");
    fscanf(f,"%i",&N);
    FOR (i,1,N) {
        fscanf(f,"%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) {
        fprintf(g,"%i\n",rez[i]);
    }
    fclose(f);fclose(g);
    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)-Query(left-1);
        if (valstanga>=poz) {
            right=mij;
        }
        else {
            poz-=valstanga;
            left=mij+1;
        }
    }
    return left;
}