Cod sursa(job #1469231)

Utilizator MaligMamaliga cu smantana Malig Data 7 august 2015 18:55:46
Problema Schi Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 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;
ifstream f("schi.in");
ofstream g("schi.out");
int N;
int v[30010],arb[65536];

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

void update(int,int,int,int);
void operation(int,int,int,int,int);
bool compar(elem,elem);

int main()
{
    f>>N;
    FOR (i,1,N) {
        f>>v[i];
        update(1,1,N,i);
    }
    //cout<<arb[6];
    ROF (i,N,1) {
        operation(1,1,N,v[i],i);
    }
    sort(sol+1,sol+N+1,compar);
    FOR (i,1,N) {
        g<<sol[i].participant<<'\n';
    }
    f.close();g.close();
    return 0;
}

void update(int nod,int st,int dr,int poz) {
    if (st==dr) {
        arb[nod]=1;
    }
    else {
        int mij=(st+dr)>>1;
        if (poz<=mij) {
            update((nod<<1),st,mij,poz);
        }
        else {
            update((nod<<1)+1,mij+1,dr,poz);
        }
        arb[nod]=arb[(nod<<1)]+arb[(nod<<1)+1];
    }
}

void operation(int nod,int st,int dr,int poz,int participant) {
    if (st==dr) {
        //cout<<participant<<' '<<st<<'\n';
        arb[nod]=0;
        sol[participant].participant=participant;
        sol[participant].poz=st;
    }
    else {
        int mij=(st+dr)>>1;
        if (arb[(nod<<1)]>=poz) {
            operation((nod<<1),st,mij,poz,participant);
        }
        else {
            poz-=arb[(nod<<1)];
            operation((nod<<1)+1,mij+1,dr,poz,participant);
        }
        arb[nod]=arb[(nod<<1)]+arb[(nod<<1)+1];
    }
}

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