Cod sursa(job #521170)

Utilizator S7012MYPetru Trimbitas S7012MY Data 11 ianuarie 2011 16:21:06
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <iostream>
#include <fstream>
#define DN 30005
using namespace std;

int n,a[4*DN],p,nr;

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

void update(int vn,int ls, int ld,int poz, int val) {
    if(ls==ld) {
        a[vn]=val;
        return;
    }
    int m=(ls+ld)>>1;
    if(poz<=m) update(vn<<1,ls,m,poz,val);
    else update((vn<<1)+1,m+1,ld,poz,val);
    a[vn]=a[vn<<1]+a[(vn<<1)+1];
}

void query(int vn,int ls, int ld,int poz) {
    if(ls==ld) {
        p=ls;
        g<<ls<<' ';
        return ;
    }
    int m=(ls+ld)>>1;
    if(nr+a[vn<<1]>=poz) query(vn<<1,ls,m,poz);
    else {
        nr+=a[1<<vn];
        query((1<<vn)+1,m+1,ld,poz);
    }

}

int main()
{

    f>>n;
    for(int i=1; i<=n; ++i) update (1,1,n,i,1);
    int x=2;
    for (int i=1; i<=n; ++i) {
        nr=0;
        query(1,1,n,x);
        update(1,1,n,p,0);
        if(a[1]>=1) x=(x+i)%a[1];
        if(0==x) x=a[1];
    }
    return 0;
}