Cod sursa(job #795104)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 7 octombrie 2012 16:22:59
Problema Farfurii Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<iostream>
#include<fstream>
using namespace std; 
const int NMAX = 100001;
int v[NMAX],arb[4*NMAX],poz,val,uval;
inline long long perm(int n)
{
	return (1LL*n*(n-1))/2;
}
void update(int nod, int st, int dr)
{
	int mij;
	if(st==dr) {
		arb[nod]=uval;
		return ;
	}
	mij=(st+dr)/2;
	if(poz<=mij)
		update(2*nod,st,mij);
	else update(2*nod+1,mij+1,dr);
	arb[nod]=arb[2*nod]+arb[2*nod+1];
}
void query(int nod, int st, int dr)
{
	int mij;
	if(st==dr) {
		val=st;
		return ;
	}
	mij=(st+dr)/2;
	if(poz<=arb[2*nod]) 
		query(2*nod,st,mij);
	else {
		poz=poz-arb[2*nod];
		query(2*nod+1,mij+1,dr);
	}
}
int main ()
{
	int n,i;
	long long k,p;
	ifstream f("farfurii.in");
	ofstream g("farfurii.out");
	f>>n>>k;
	f.close();
	uval=1;
	for(i=1;i<=n;i++) {
		poz=i;
		update(1,1,n);
	}
	uval=0;
	for(i=1;i<=n;i++) {
		p=perm(n-i);
		if(p==k)
			break;
		else if(p>k) {
			poz=1;
			query(1,1,n);
			g<<val<<" ";
			v[val]=1;
			poz=val;
			update(1,1,n);
		}
		else {
			poz=0LL+k-p+1;
			k=0LL+k-poz+1;
			query(1,1,n);
			g<<val<<" ";
			v[val]=1;
			poz=val;
			update(1,1,n);
		}
	}
	for(i=n;i>=1;i--)
		if(v[i]==0)
			g<<i<<" ";
	g<<'\n';
	g.close();
	return 0;
}