Cod sursa(job #479524)

Utilizator CezarMocanCezar Mocan CezarMocan Data 24 august 2010 13:00:48
Problema Congr Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>

const int maxP = 300100;

using namespace std;

int P;
int A[2 * maxP];
int M1[maxP], M2[maxP], f1[maxP], f2[maxP], sum;

int main() {
	int i, p1, p2, search;

	srand(time(0));

	freopen("congr.in", "r", stdin);
	freopen("congr.out", "w", stdout);

	scanf("%d", &P);
	for (i = 1; i <= 2 * P - 1; i++) {
		scanf("%d", &A[i]);
		A[i] %= P;
	}
	
	for (i = 1; i <= P; i++) {
		M1[i] = i;
		f1[A[i]]++;
		sum = (sum + A[i]) % P;
	}

	for (i = P + 1; i <= 2 * P - 1; i++) {
		M2[i - P] = i;
		f2[A[i]]++;
	}

	while (1) {
		p1 = rand() % P + 1;
		sum = sum - A[M1[p1]];
		if (sum < 0)	sum += P;
		search = (P - sum) % P;

		if (f2[search]) {
			for (i = 1; i <= P - 1; i++)
				if (A[M2[i]] == search) {
					printf("%d ", M2[i]);
					i = P;
					break;
				}

			for (i = 1; i <= P; i++)
				if (i != p1)
					printf("%d ", M1[i]);
			return 0;
		}

		p2 = rand() % (P - 1) + 1;

		f1[A[M1[p1]]]--;
		f2[A[M1[p1]]]++;

		f1[A[M2[p2]]]++;
		f2[A[M2[p2]]]--;

		swap(M1[p1], M2[p2]);
		sum = (sum + A[M1[p1]]) % P;
	}

	return 0;
}