Cod sursa(job #1349414)

Utilizator bogdanpaunFMI Paun Bogdan Gabriel bogdanpaun Data 20 februarie 2015 10:41:52
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <fstream>
using namespace std;

ifstream f("order.in");
ofstream g("order.out");

int n;
#define N 30005
int a[N],q=1;
int m,nr,ps=2;
void update(int pos ,int val){
    for(;pos<=n;pos+=pos&-pos) a[pos]+=val;
}


int query(int pos){
    int sol=0;
    for(;pos;pos-=pos&-pos) sol +=a[pos];
    return sol;
}


int main()
{
    f >> n;
    for(int i=1;i<=n;++i) update(i,1);
    nr = n;
    for(int i=1;i<=n;++i){
        --nr;
        int sol = 0;
        int p=1<<14;
        for(;p;p>>=1){
            if( sol + p <= n && query(sol+p) < ps  )
                sol +=p;
        }

        ++sol;
        g << sol << " ";
        update(sol,-1);
        ps+=i;
        if( nr ) ps%=nr;
        if(!ps ) ps = nr;
    }


    return 0;
}