Cod sursa(job #1224349)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 30 august 2014 17:48:19
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include<iostream>
#include<fstream>
#include<string.h>
#include<assert.h>
using namespace std;

#define NMAX 30001

int a[4*NMAX+1],sol[NMAX],sum;

void built(int nod, int st, int dr)
{
	int mij;
	if(st==dr) {
		a[nod]=1;
		return ;
	}
	mij=(st+dr)/2;
	built(nod*2,st,mij);
	built(nod*2+1,mij+1,dr);
	a[nod]=a[nod*2]+a[nod*2+1];
}

void update(int nod, int st, int dr, int poz) 
{
	int mij;
	if(st==dr) {
		a[nod]=0;
		return ;
	}
	mij=(st+dr)/2;
	if(poz<=mij)
		update(nod*2,st,mij,poz);
	else update(nod*2+1,mij+1,dr,poz);
	a[nod]=a[nod*2]+a[nod*2+1];
}

void query1(int nod, int st, int dr, int aa, int bb)
{
	int mij;
	if(aa<=st && dr<=bb) {
		sum=sum+a[nod];
		return ;
	}
	mij=(st+dr)/2;
	if(aa<=mij)
		query1(nod*2,st,mij,aa,bb);
	if(mij<bb)
		query1(nod*2+1,mij+1,dr,aa,bb);
}

int query2(int nod, int st, int dr, int x)
{
	int mij;
	if(st==dr)
		return st;
	mij=(st+dr)/2;
	if(x<=a[nod*2])
		return query2(nod*2,st,mij,x);
	else return query2(nod*2+1,mij+1,dr,x-a[nod*2]);
}

void solve(int n)
{
	int i,s,k,x,p;
	built(1,1,n);
	k=2;
	s=n;
	for(i=1;i<=n;i++) {
		sum=0;
		query1(1,1,n,k,n);
		x=i;
		if(x>sum) {
			k=query2(1,1,n,1);
			x=x-sum;
		}
		else {
			sum=0;
			if(k>=2)
				query1(1,1,n,1,k-1);
			k=query2(1,1,n,1);
			x=x+sum;
		}
		if(x>s) {
			p=x/s;
			x=x-p*s;
			if(x==0)
				x=s;
		}
		assert(x<=s);
		k=query2(1,1,n,x);
		sol[i]=k;
		update(1,1,n,k);
		sum=0;
		query1(1,1,n,1,k);
		k=query2(1,1,n,sum+1);
		s--;
	}
}

int main ()
{
	int n,i;
	ifstream f("order.in");
	ofstream g("order.out");
	f>>n;
	f.close();
	solve(n);
	for(i=1;i<=n;i++) 
		g<<sol[i]<<" ";
	g.close();
	return 0;
}