Cod sursa(job #1794415)

Utilizator DobosDobos Paul Dobos Data 1 noiembrie 2016 11:50:41
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <bits/stdc++.h>

const int NMAX = 30005;

using namespace std;

ifstream fin("order.in");
ofstream fout("order.out");

int V[4*NMAX],v[NMAX],S,n;

void buildtree(int nod,int l,int r){
    if(l == r){
        V[nod] = 1;
        return;
    }
    int mid = (l + r) / 2;
    buildtree(2 * nod, l , mid);
    buildtree(2 * nod + 1, mid + 1, r);

    V[nod] = V[2 * nod] + V[2 * nod +1];
}
void update(int nod,int l,int r,int poz,int j,int &ok){
    if(l == r){
        V[nod] = 0;
        v[j] = l;
        ok = 0;
        return ;
    }
    int mid = (l + r) / 2;

    if(mid < poz && ok != 0)
        update(2 * nod + 1,mid + 1,r,poz,j,ok);
    if(mid >= poz && ok != 0)
        update(2 * nod,l,mid,poz,j,ok);

    V[nod] = V[2 * nod] + V[2 * nod +1];

}



void query(int nod,int l,int r,int i,int j){

    if(S >= V[nod] && l >= i && l <= r){
        S -= V[nod];
        if(S == 0){
            int ok = 1;
            update(1,1,n,r,j,ok);
        }
        return;
    }
    if(l >= r)
        return;

    int mid = (l + r) / 2;
    query(2 * nod,l,mid,i,j);
    query(2 * nod + 1,mid + 1, r,i,j);

}


int main()
{
    ios :: sync_with_stdio(false);
    fin.tie(NULL);

    fin >> n;

    buildtree(1,1,n);

    for(int i = 1,j = 1; j <= n; j++){
        S = j + 1;
        query(1,1,n,i,j);
        fout << v[j];
    }
    return 0;
}