Pagini recente » Cod sursa (job #2577823) | Cod sursa (job #2872164) | Cod sursa (job #1361945) | Cod sursa (job #1193519) | Cod sursa (job #466709)
Cod sursa(job #466709)
#include <algorithm>
#include <stdio.h>
#include <time.h>
using namespace std;
#define BRUTE_LIMIT 2000
#define DIM 300005
#define sc second
#define fs first
pair <int,int> v[DIM<<1];
double start;
int p,n,nrp;
int s[DIM];
void read ()
{
int i;
scanf ("%d",&p);
for (i=1; i<(p<<1); ++i)
{
scanf ("%d",&v[i].fs);
v[i].sc=i;
}
}
void solve_brute ()
{
int i,j,k,ok;
n=(p<<1)-1;
sort (v+1,v+n+1);
do
{
ok=0;
for (i=1; i<=n; ++i)
{
s[i]=(s[i-1]+v[i].fs)%p;
if (!s[i] && i<=p-nrp)
{
nrp+=i;
for (j=1; j<=i; ++j)
printf ("%d ",v[j].sc);
for (j=i+1; j<=n; ++j)
v[j-i]=v[j];
n-=i;
ok=1;
}
}
for (i=1; i<n && !ok; ++i)
for (j=i+1; j<=n && !ok; ++j)
if (s[j]==s[i] && !ok && j-i<=p-nrp)
{
nrp+=j-i;
for (k=i+1; k<=j; ++k)
printf ("%d ",v[k].sc);
for (k=j+1; k<=n; ++k)
v[i+k-j]=v[k];
n-=j-i;
ok=1;
}
}
while (nrp<p);
}
void solve_bulan ()
{
int i,sum;
while ((clock()-start)/CLOCKS_PER_SEC<0.75)
{
sum=0;
random_shuffle (v+1,v+(p<<1));
for (i=1; i<=p; ++i)
sum+=v[i].fs;
if (!(sum%p))
{
for (i=1; i<=p; ++i)
printf ("%d ",v[i].sc);
return ;
}
}
random_shuffle (v+1,v+(p<<1));
for (i=1; i<=p; ++i)
printf ("%d ",v[i].sc);
}
int main ()
{
start=clock ();
freopen ("congr.in","r",stdin);
freopen ("congr.out","w",stdout);
read ();
if (p<=BRUTE_LIMIT)
solve_brute ();
else
solve_bulan ();
return 0;
}