Cod sursa(job #466690)

Utilizator savimSerban Andrei Stan savim Data 27 iunie 2010 13:17:33
Problema Congr Scor 50
Compilator cpp Status done
Runda Stelele Informaticii 2010, clasele X-XII, Ziua 1 Marime 1.38 kb
#include <stdio.h>
#include <vector>
#include <string.h>

using namespace std;

#define MAX_N 300010

int p;
int A[MAX_N], sum[MAX_N];
int c[310][310], vine[310][310];

vector <int> rest[MAX_N];

void solve20() {
	c[0][0] = 1;
	for (int i = 1; i < 2 * p - 1; i++)
		for (int j = 0; j < p; j++)
			for (int k = 0; k < p; k++)
				if (c[j][k] && c[(j + A[i]) % p][k + 1] == 0 && vine[j][k] != i) {
                	c[(j + A[i]) % p][k + 1] = 1;
					vine[(j + A[i]) % p][k + 1] = i;
				}

	int x = 0, y = p;	
	while (vine[x][y]) {
		printf("%d ", vine[x][y]);
		
		x = (x - A[vine[x][y]]) % p;
		if (x < 0) x += p;

		y--;
	}
	printf("\n");
}

int main() {

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

	scanf("%d", &p);
	for (int i = 1; i < 2 * p; i++)
		scanf("%d", &A[i]);

	if (p <= 300)
		solve20();
    else {   
    	//sol 1
        for (int i = 1; i < 2 * p; i++)
			sum[i] = (sum[i - 1] + A[i]) % p;
		for (int i = p; i < 2 * p; i++)
			if (sum[i] == sum[i - p]) {
            	for (int j = i - p + 1; j <= i; j++)
					printf("%d ", j);
				printf("\n");

				return 0;
			}
		
		//sol 2
		for (int i = 1; i < 2 * p; i++)	
			rest[A[i] % p].push_back(i);
		for (int i = 0; i < 2 * p; i++) {
			int len = rest[i].size();
			if (len >= p) {
            	for (int j = 0; j < p; j++)
					printf("%d ", rest[i][j]);
				printf("\n");

				return 0;
			}
		}
	}
	

	return 0;
}