Cod sursa(job #466802)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 27 iunie 2010 14:58:32
Problema Congr Scor 80
Compilator cpp Status done
Runda Stelele Informaticii 2010, clasele X-XII, Ziua 1 Marime 1.58 kb
#include<cstdio>
#include<algorithm>
#define infile "congr.in"
#define outfile "congr.out"
#define nmax 600013

using namespace std;

int v[nmax]; //sirul cu numerele
int r[nmax]; //r[i]=v[i]%p
int poz[nmax]; //poz[i]=pozitia din r al celui de-al i-lea element sortat
char viz[nmax]; //sa stim ce numere avem selectate
int sum; //suma celor mai mici p elemente din r modulo p
int p; //numarul de numere ce trebuie gasite
int n; //numarul total de numere

inline bool cmp(int i, int j)
{
	return (r[i]<r[j]);
}

void read()
{
	int i;
	scanf("%d\n",&p);
	n=(p<<1)-1;
	for(i=1;i<=n;++i)
		scanf("%d",&v[i]);
}

void init()
{
	int i;

	//initializam pe r
	for(i=1;i<=n;++i)
		r[i]=v[i]%p;

	//initializam pe poz
	for(i=1;i<=n;i++)
		poz[i]=i;

	//sortam pe r in functie de poz
	sort(poz+1, poz+1+n, cmp);

	//initializam sum
	for(i=1;i<=p;++i)
		sum=(sum+r[poz[i]])%p;

	//initializam viz
	for(i=1;i<=p;i++)
		viz[r[poz[i]]]=1;

	/*
	for(i=1;i<=n;++i)
		printf("%d ",r[poz[i]]);
	printf("\n");
	*/
}

void solve()
{
	//daca suntem norocosi :>
	if(!sum) return;

	//cat trebuie sa mai adaugam la suma
	int dif=p-sum;
	int i,j,k;

	//incercam prin schimbarea unui singur numar
	for(i=p+1;i<=n;++i)
		if(r[poz[i]]-dif>=0 && viz[r[poz[i]]-dif])
		{
			k=r[poz[i]]-dif;
			for(j=1;j<=p;++j)
				if(r[poz[j]]==k) //VICTORIEE :))
				{
					poz[j]=poz[i];
					j=p,i=n;
				}
		}
}

void write()
{
	int i;
	for(i=1;i<=p;++i)
		printf("%d ",poz[i]);
	printf("\n");
}

int main()
{
	freopen(infile,"r",stdin);
	freopen(outfile,"w",stdout);

	read();
	init();
	solve();
	write();

	fclose(stdin);
	fclose(stdout);
	return 0;
}