Cod sursa(job #467352)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 28 iunie 2010 14:41:56
Problema Congr Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <ctime>
#include <cstring>
#include <stdlib.h>
#define MAXN 300010

using namespace std;

int A[2 * MAXN + 100], right, x, m, r1, px, py, sum, gr1[MAXN], cnt, nr, i, ok, P;
int cl[2 * MAXN + 100];
int main ()
{
	freopen ("congr.in", "r", stdin);
	freopen ("congr.out", "w", stdout);
	scanf ("%d\n", &P);
	const int n = 2 * P - 1;
	for (i = 1; i <= n; i++)
	{
		scanf ("%d", &A[i]);
		cl[i] = i;
	}
	m = n;
	srand (time (NULL));
	while (nr < P)
	{
		++nr;
		x = rand () % m + 1;
		gr1[nr] = cl[x];
		sum = (sum + A[gr1[nr]]) % P;
		cl[x] = cl[m--];
	}
	int r1, r2;
	//for (i = 1; i <= P; i++) printf ("%d ",gr1[i]);
	//printf ("\n");
	//for (i = 1; i <= m; i++) printf ("%d ", cl[i]);
//	ok = 1;
	//printf ("\n%d\n", sum);
	//printf ("%d %d\n", P, m);
	ok = 0;
	while (!ok)
	{	
		r1 = sum % P;
		px = rand () % P + 1;
		px = rand () % m + 1;
		r2 = sum - A[gr1[px]] + A[cl[py]];
		r2 %= P;
		if (r1 > r2) 
		{
			swap (gr1[px], cl[py]);
			sum = sum - A[cl[py]] + A[gr1[px]];
		}
		if (sum % P == 0) ok = 1;
	}
	for (i = 1; i <= P; i++)
		printf ("%d ", gr1[i]);
	return 0;
}