Cod sursa(job #1204257)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 2 iulie 2014 15:19:57
Problema Order Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include<iostream>
#include<fstream>
using namespace std;

#define NMAX 30001

int a[4*NMAX+1],v[NMAX],sol,aa,b;

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]=1-a[nod];
		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 query(int nod, int st, int dr)
{
	int mij;
	if(aa<=st && dr<=b) {
		sol=sol+a[nod];
		return;
	}
	mij=(st+dr)/2;
	if(aa<=mij)
		query(nod*2,st,mij);
	if(mij<b)
		query(nod*2+1,mij+1,dr);
}

int cbin(int last, int s, int all, int n)
{
	int q,mij,p,first,nr,nrr;
	q=n*(n+1);
	p=last;
	aa=p;
	b=n;
	sol=0;
	query(1,1,n);
	nrr=sol;
	while(p<=q) {
		mij=(p+q)/2;
		if(mij<=n) {
			aa=last;
			b=mij;
			sol=0;
			query(1,1,n);
		}
		else {
			first=(mij/n)*n;
			if(first)
				sol=all*(first/n-1);
			else sol=0;
			if(mij>n)
				sol=sol+nrr;
			first=mij%n;
			if(first) {
				nr=sol;
				aa=1;
				b=first;
				sol=0;
				query(1,1,n);
				sol=sol+nr;
			}	
		}
		if(sol==s) {
			if(mij%n==0)
				nr=n;
			else nr=mij%n;
			if(v[nr])
				return nr;
			else q=mij-1;
		}
		else if(sol<s)
			p=mij+1;
		else q=mij-1;
	}
	return 0;
}

int main ()
{
	int poz,i,q,mij,n,all,last;
	ifstream f("order.in");
	ofstream g("order.out");
	f>>n;
	f.close();
	built(1,1,n);
	for(i=1;i<=n;i++)
		v[i]=1;
	g<<"2 ";
	update(1,1,n,2);
	all=n-1;
	last=3;
	if(n==2)
		last=1;
	v[2]=0;
	for(i=2;i<=n;i++) {
		poz=cbin(last,i,all,n);
		g<<poz<<" ";
		all--;
		update(1,1,n,poz);
		v[poz]=0;
		last=poz+1;
		if(last>n)
			last=1;
	}
	g.close();
	return 0;
}