Cod sursa(job #466893)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 27 iunie 2010 20:53:11
Problema Congr Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <ctime>
#include <cstring>

#define MAXN 300010

using namespace std;

int A[MAXN], right, x, m, r1, px, py, sum, gr1[MAXN/2], gr2[MAXN/2], cnt, nr, ok, P, i;
int cl[MAXN];
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 (0);
	while (nr != P)
	{
		x = rand () % m + 1;
		gr1[++cnt] = x;
		swap (cl[x], cl[m--]);
		++nr;
	}
	for (i = 1; i <= m; i++) gr2[i] = cl[i];
	for (i = 1; i <= P; i++) sum += A[gr1[i]];
	while (!ok)
	{	
		r1 = sum % P;
		px = rand () % P + 1;
		py = rand () % m + 1;
		sum -= A[gr1[px]];
		sum += A[gr2[py]];
		if (sum % P < r1) swap (gr1[px], gr2[py]);
		if (sum % P == 0) ok = 1;
	}
	for (i = 1; i <= P; i++)
		printf ("%d ", gr1[i]);
	return 0;
}