Cod sursa(job #467360)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 28 iunie 2010 15:07:54
Problema Congr Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <ctime>
#include <cstring>
#include <stdlib.h>
#define MAXN 300010
#define dim 8192
using namespace std;

int A[2 * MAXN + 100], right, x, m, r1, px, py, sum, gr1[MAXN], cnt, nr, i, ok, p;
int IND[2 * MAXN + 100], R, L, gr2[MAXN];

char ax[dim];
int pz;

void cit (int &x)
{
	x = 0;

	while (ax[pz] < '0' || ax[pz] > '9')
		if (++pz == dim)
			fread (ax, 1, dim, stdin),pz = 0;

	while (ax[pz] >= '0' && ax[pz] <= '9')
	{
		 x = x * 10 + ax[pz] - '0';
		 if (++pz == dim)
			 fread (ax, 1, dim, stdin),pz =0;
	}

}

inline bool cmp (const int &a, const int &b)
{
	return A[a] > A[b];
}

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++)
	{
		cit (A[i]);
		IND[i] = i;
	}
	srand (time (NULL));
	random_shuffle (IND + 1, IND + n + 1);
	sort (IND + 1, IND + n + 1, cmp);
	m = n;
	for (i = 1; i <= p; i++)
		gr1[++L] = IND[i], sum = (sum + A[IND[i]]) % p;
	for (i = p + 1; i <= n; i++)
		gr2[++R] = IND[i];

	int r1, r2;
	for (; ; )
	{
		px = rand () % L + 1;
		py = rand () % R + 1;
		r1 = sum % p;
		r2 = (sum - A[gr1[px]] + A[gr2[py]] + p) % p;
		if (r1 > r2)
		{
			sum = (sum - A[gr1[px]] + p) % p;
			sum += A[gr2[py]];
			swap (gr1[px], gr2[py]);
		}
		sum %= p;
		if (sum == 0) break;
	}
	for (i = 1; i <= p; i++)
		printf ("%d ", gr1[i]);
	return 0;
}