Cod sursa(job #1469248)

Utilizator MaligMamaliga cu smantana Malig Data 7 august 2015 20:06:22
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 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];

struct elem {
    short poz,participant;
}sol[30010];

void Update(int,int);
int Query(int);
int Search(int);
bool compar(elem,elem);

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]);
        sol[i].participant=i;
        sol[i].poz=val;
        Update(val,-1);
    }
    sort(sol+1,sol+N+1,compar);
    FOR (i,1,N) {
        fprintf(g,"%i\n",sol[i].participant);
    }
    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)/2;
        if (Query(mij)-Query(left-1)>=poz) {
            right=mij;
        }
        else {
            poz-=(Query(mij)-Query(left-1));
            left=mij+1;
        }
    }
    return left;
}

bool compar(elem a,elem b) {
    return a.poz<b.poz;
}