Cod sursa(job #1449739)

Utilizator MaarcellKurt Godel Maarcell Data 10 iunie 2015 15:13:18
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <iostream>
#include <fstream>
using namespace std;

int N,tree[60000];

void update(int pos){
    for (; pos<=N; pos+=(pos&-pos))
        tree[pos]--;
}

int gets(int pos){
    int res=0;
    for (; pos; pos-=(pos&-pos))
        res+=tree[pos];
    return res;
}

int suma(int l, int r){
    return gets(r)-gets(l-1);
}

int get(int sum){
    int l=1,r=N,mid;
    while (l<r){
        mid=(l+r)/2;
        if (gets(mid)>=sum) r=mid;
        else l=mid+1;
    }

    return r;
}

int main(){
    ifstream fin("order.in");
    ofstream fout("order.out");
    fin >> N;

    int i,x,p=2;
    for (i=1; i<=N; i++)
        tree[i]=i&-i;

    update(2);
    fout << 2 << " ";

    for (i=2; i<=N; i++){
        x=i%(N-i+1);
        if (x==0) x=N-i+1;

        if (suma(p,N)>=x)
            x+=gets(p);
        else x-=suma(p,N);

        p=get(x);
        update(p);
        fout << p << " ";
    }

    fout << "\n";
    return 0;
}