Pagini recente » Cod sursa (job #1903285) | Cod sursa (job #2664958) | Cod sursa (job #2546931) | Cod sursa (job #766198) | Cod sursa (job #466858)
Cod sursa(job #466858)
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#define dim 8192
using namespace std;
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;
}
}
struct nod
{
int x, poz;
};
struct cmp
{
bool operator () (const nod &a, const nod &b)const
{
if (a.x < b.x) return 1;
return 0;
}
};
int v[600001];
nod a[600001];
int n, m;
int left[300001], right[300001];
int nl, nr;
void solve ()
{
sort (a + 1, a + m + 1, cmp () );
int i, j;
nl = nr = 0;
for (i = 1; i <= n; ++i)
left[++nl] = a[i].poz;
for (i = n + 1; i <= m; ++i)
right[++nr] = a[i].poz;
int rest = 0;
for (i = 1; i <= nl; ++i)
rest = (rest + v[left[i]] ) % n;
int ntimes ;
int restNou;
int p, q;
int aux;
for (ntimes = 0; ; ++ntimes)
{
if (rest == 0)
break;
p = rand () % nl + 1;
q = rand () % nr + 1;
restNou = rest;
restNou = ((restNou - v[left[p]]) % n + n) % n;
restNou = (restNou + v[right[q]]) % n;
if (restNou < rest)
{
aux = left[p];
left[p] = right[q];
right[q] = aux;
rest = restNou;
}
}
sort (left + 1, left + nl + 1);
for (i = 1;i <= nl; ++i)
printf ("%d ", left[i]);
printf ("\n");
// fprintf (stderr, "(%d)\n",rest);
}
int main ()
{
srand (time (0));
freopen ("congr.in", "r", stdin);
freopen ("congr.out", "w", stdout);
cit (n);
m = 2 * n - 1;
int i;
for (i = 1; i <= m; ++i)
{
cit (a[i].x);
v[i] = a[i].x;
a[i].poz = i;
}
solve ();
return 0;
}