Cod sursa(job #1797347)

Utilizator DobosDobos Paul Dobos Data 4 noiembrie 2016 11:46:19
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 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;

    fin >> n;

    buildtree(1,1,n);

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

    }


    return 0;
}