Pagini recente » Cod sursa (job #1828250) | Cod sursa (job #2664174) | Cod sursa (job #1759072) | Cod sursa (job #3230459) | Cod sursa (job #467359)
Cod sursa(job #467359)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <ctime>
#include <cstring>
#include <stdlib.h>
#define MAXN 300010
#define dim 8192
using namespace std;
int A[2 * MAXN + 100], right, x, m, r1, px, py, sum, gr1[MAXN], cnt, nr, i, ok, p;
int IND[2 * MAXN + 100], R, L, gr2[MAXN];
char ax[dim];
int pz;
void cit (int &x)
{
x = 0;
while (ax[pz] < '0' || ax[pz] > '9')
if (++pz == dim)
fread (ax, 1, dim, stdin),pz = 0;
while (ax[pz] >= '0' && ax[pz] <= '9')
{
x = x * 10 + ax[pz] - '0';
if (++pz == dim)
fread (ax, 1, dim, stdin),pz =0;
}
}
inline bool cmp (const int &a, const int &b)
{
return A[a] > A[b];
}
int main ()
{
freopen ("congr.in", "r", stdin);
freopen ("congr.out", "w", stdout);
scanf ("%d\n", &p);
const int n = 2 * p - 1;
for (i = 1; i <= n; i++)
{
cit (A[i]);
IND[i] = i;
}
random_shuffle (IND + 1, IND + n + 1);
sort (IND + 1, IND + n + 1, cmp);
m = n;
for (i = 1; i <= p; i++)
gr1[++L] = IND[i], sum = (sum + A[IND[i]]) % p;
for (i = p + 1; i <= n; i++)
gr2[++R] = IND[i];
int r1, r2;
srand (time (NULL));
for (; ; )
{
px = rand () % L + 1;
py = rand () % R + 1;
r1 = sum % p;
r2 = (sum - A[gr1[px]] + A[gr2[py]] + p) % p;
if (r1 > r2)
{
sum = (sum - A[gr1[px]] + p) % p;
sum += A[gr2[py]];
swap (gr1[px], gr2[py]);
}
sum %= p;
if (sum == 0) break;
}
for (i = 1; i <= p; i++)
printf ("%d ", gr1[i]);
return 0;
}