Cod sursa(job #1036241)

Utilizator enedumitruene dumitru enedumitru Data 19 noiembrie 2013 06:42:49
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <fstream>
using namespace std;
ifstream f("order.in"); ofstream g("order.out");
const int Dmax=30001; 
int n,nr,p,a[3*Dmax];
void update(int vn,int ls, int ld,int poz, int val)
{   if(ls==ld) a[vn]=val;
	else 
	{	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<<' ';
    else
	{	int m=(ls+ld)>>1;
		if(nr+a[vn<<1]>=poz)   query(vn<<1,ls,m,poz);
			else nr+=a[vn<<1], query((vn<<1)+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(x==0) x=a[1];
    }
    g.close(); return 0;
}