Pagini recente » Cod sursa (job #1416186) | Cod sursa (job #1931322) | Rating Keylos Key (Keylos) | Cod sursa (job #108607) | Cod sursa (job #466802)
Cod sursa(job #466802)
#include<cstdio>
#include<algorithm>
#define infile "congr.in"
#define outfile "congr.out"
#define nmax 600013
using namespace std;
int v[nmax]; //sirul cu numerele
int r[nmax]; //r[i]=v[i]%p
int poz[nmax]; //poz[i]=pozitia din r al celui de-al i-lea element sortat
char viz[nmax]; //sa stim ce numere avem selectate
int sum; //suma celor mai mici p elemente din r modulo p
int p; //numarul de numere ce trebuie gasite
int n; //numarul total de numere
inline bool cmp(int i, int j)
{
return (r[i]<r[j]);
}
void read()
{
int i;
scanf("%d\n",&p);
n=(p<<1)-1;
for(i=1;i<=n;++i)
scanf("%d",&v[i]);
}
void init()
{
int i;
//initializam pe r
for(i=1;i<=n;++i)
r[i]=v[i]%p;
//initializam pe poz
for(i=1;i<=n;i++)
poz[i]=i;
//sortam pe r in functie de poz
sort(poz+1, poz+1+n, cmp);
//initializam sum
for(i=1;i<=p;++i)
sum=(sum+r[poz[i]])%p;
//initializam viz
for(i=1;i<=p;i++)
viz[r[poz[i]]]=1;
/*
for(i=1;i<=n;++i)
printf("%d ",r[poz[i]]);
printf("\n");
*/
}
void solve()
{
//daca suntem norocosi :>
if(!sum) return;
//cat trebuie sa mai adaugam la suma
int dif=p-sum;
int i,j,k;
//incercam prin schimbarea unui singur numar
for(i=p+1;i<=n;++i)
if(r[poz[i]]-dif>=0 && viz[r[poz[i]]-dif])
{
k=r[poz[i]]-dif;
for(j=1;j<=p;++j)
if(r[poz[j]]==k) //VICTORIEE :))
{
poz[j]=poz[i];
j=p,i=n;
}
}
}
void write()
{
int i;
for(i=1;i<=p;++i)
printf("%d ",poz[i]);
printf("\n");
}
int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);
read();
init();
solve();
write();
fclose(stdin);
fclose(stdout);
return 0;
}