Pagini recente » Cod sursa (job #2158145) | Cod sursa (job #1465372) | Cod sursa (job #1837100) | Cod sursa (job #318630) | Cod sursa (job #479524)
Cod sursa(job #479524)
#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;
}