Pagini recente » Cod sursa (job #545561) | Cod sursa (job #978584) | Cod sursa (job #3184125) | Cod sursa (job #475952) | Cod sursa (job #466690)
Cod sursa(job #466690)
#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;
}