Cod sursa(job #466766)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 27 iunie 2010 14:30:01
Problema Congr Scor 100
Compilator cpp Status done
Runda Stelele Informaticii 2010, clasele X-XII, Ziua 1 Marime 0.96 kb
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <bitset>
#include <assert.h>

using namespace std;

#define maxN 	600100

bitset <maxN> luat;
int V[maxN], N;

int main () {
	int i, x, y, Sum = 0;

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

	scanf("%d", &N);

	srand(time(NULL)); // hai cu bulanu

	for (i = 1; i < 2 * N; ++ i)
		scanf("%d", &V[i]);

	for (i = 1; i <= N; ++ i) {
		do {
			x = rand () % (2 * N - 1) + 1;
		} while (luat[x]);
		luat[x] = 1;
		Sum = (Sum + V[x]) % N;
	}

	while (Sum != 0) {
		do {
			x = rand () % (2 * N - 1) + 1;
			y = rand () % (2 * N - 1) + 1;
		} while (! luat[x] || luat[y]);
		assert(luat[x] && ! luat[y] && x != y);
		Sum = (Sum + N + V[y] - V[x]) % N;
		luat[x] = 0;
		luat[y] = 1;
	}
/*
	int Sol = 0, sum = 0;
	for (i = 1; i < 2 * N; ++ i)
		if (luat[i]) {
			Sol ++;
			sum += V[i];
		}
	printf("%d %d\n", Sol, sum % N);
*/	
	for (i = 1; i < 2 * N; ++ i)
		if (luat[i])
			printf("%d ", i);
}