Pagini recente » Cod sursa (job #1146536) | Cod sursa (job #528339) | Cod sursa (job #1192465) | Cod sursa (job #1635687) | Cod sursa (job #479420)
Cod sursa(job #479420)
#include <fstream>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;
const int PMAX=300003;
int P,x[2*PMAX],a[PMAX],b[PMAX],nr[PMAX];
int main()
{
int i,j;
ifstream fin("congr.in");
fin>>P;
for (i=1;i<=2*P-1;++i)
{
fin>>x[i];
x[i]%=P;
}
int sum=0;
for (i=1;i<=P;++i)
{
a[i]=i;
sum=sum+x[i];
if (sum>=P) sum-=P;
}
for (;i<=2*P-1;++i)
{
b[i-P]=i;
++nr[x[i]];
}
srand(time(0));
while (sum!=0)
{
int p=rand()%P + 1;
sum-=x[a[p]];
if (sum<0) sum+=P;
int rest=P-sum;
if (rest==P) rest=0;
if (nr[rest]>0)
{
for (j=1;j<=P-1;++j)
if (x[b[j]]==rest) break;
}
else
{
j=rand()%(P-1) + 1;
}
int tmp=a[p];a[p]=b[j];b[j]=tmp;
--nr[x[a[p]]];++nr[x[b[j]]];
sum+=x[a[p]];
if (sum>=P) sum-=P;
}
ofstream fout("congr.out");
for (i=1;i<=P;++i) fout<<a[i]<<" ";
return 0;
}