Cod sursa(job #1799984)

Utilizator DobosDobos Paul Dobos Data 7 noiembrie 2016 09:25:24
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <bits/stdc++.h>

const int NMAX = 30005;

using namespace std;

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

int n,V[4 * NMAX];


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){
    if(l == r){
        V[nod] = 0;
        return;
    }
    int mid = (l + r) / 2;

    if(poz <= mid)
        update(2 * nod,l,mid,poz);
    else
        update(2 * nod + 1,mid + 1,r,poz);

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


int  query(int nod,int l,int r, int S){
    if(l == r){
        update(1,1,n,l);
        return l;
    }
    int mid = (l + r)/2;

    if(V[2 * nod] >= S)
        return query(2 * nod,l,mid,S);
    else
        return query(2 * nod + 1,mid + 1, r, S - V[2 * nod]);

}

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

    int S = 1,p = 0;

    fin >> n;

    buildtree(1,1,n);
    for(int i = 1, j = 1; j <= n ; j++){
       S += j  - p;
       while(S > V[1])
            S -= V[1] ;
         i = query(1,1,n,S);
            p = 1;
         fout << i << " ";

    }


    return 0;
}