Cod sursa(job #479420)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 23 august 2010 22:49:51
Problema Congr Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;

const int PMAX=300003;

int P,x[2*PMAX],a[PMAX],b[PMAX],nr[PMAX];

int main()
{
	int i,j;
	ifstream fin("congr.in");
	fin>>P;
	for (i=1;i<=2*P-1;++i)
	{
		fin>>x[i];
		x[i]%=P;
	}
	
	int sum=0;
	for (i=1;i<=P;++i)
	{
		a[i]=i;
		sum=sum+x[i];
		if (sum>=P) sum-=P;
	}

	for (;i<=2*P-1;++i)
	{
		b[i-P]=i;
		++nr[x[i]];
	}

	srand(time(0));

	while (sum!=0)
	{
		int p=rand()%P + 1;
		sum-=x[a[p]];
		if (sum<0) sum+=P;
		int rest=P-sum;
		if (rest==P) rest=0;
		if (nr[rest]>0)
		{
			for (j=1;j<=P-1;++j)
				if (x[b[j]]==rest) break;
		}
		else
		{
			j=rand()%(P-1) + 1;
		}
		int tmp=a[p];a[p]=b[j];b[j]=tmp;
		--nr[x[a[p]]];++nr[x[b[j]]];
		sum+=x[a[p]];
		if (sum>=P) sum-=P;
	}

	ofstream fout("congr.out");
	for (i=1;i<=P;++i) fout<<a[i]<<" ";

	return 0;
}