Pagini recente » Cod sursa (job #1058119) | Cod sursa (job #1120872) | Cod sursa (job #748436) | Cod sursa (job #368006) | Cod sursa (job #466916)
Cod sursa(job #466916)
#include<fstream>
#include<cstdlib>
using namespace std;
const char iname[]="congr.in";
const char oname[]="congr.out";
const int maxn=300005;
ifstream f(iname);
ofstream g(oname);
int a[maxn],s[maxn],d[maxn],i,n,p,s1,s2,step,leftv[maxn],rightv[maxn],orn,pasi;
int rez1()
{
for(i=1;i<=n;++i)
{
f>>a[i];s[i]=i;a[i]%=n;
s1+=a[i];
if(s1>=n)
s1-=n;
++leftv[a[i]];
}
orn=n;
n*=2;
--n;
for(p=1;i<=n;++i,++p)
{
f>>a[i];d[p]=i;a[i]%=orn;
s2+=a[i];
if(s2>=orn)
s2-=orn;
++rightv[a[i]];
}
n=(n+1)/2;
srand(time(0));
step=1;
while((step==2||s1!=0)&&(step==1||s2!=0))
{
++pasi;
if(step==1)
if(leftv[n-s2])
{
for(i=1;i<=n;++i)
if(a[s[i]]==n-s2)
{
d[n]=s[i];
break;
}
s2=0;
step=2;
break;
}
else
{
p=rand()%n+1;
d[n]=s[p];
s[p]=s[n];
s1-=a[d[n]];
--leftv[a[d[n]]];
++rightv[a[d[n]]];
if(s1<0)
s1+=n;
s2+=a[d[n]];
if(s2>=n)
s2-=n;
step=2;
}
else
if(rightv[n-s1])
{
for(i=1;i<=n;++i)
if(a[d[i]]==n-s1)
{
s[n]=d[i];
break;
}
step=1;
s1=0;
break;
}
else
{
p=rand()%n+1;
s[n]=d[p];
d[p]=d[n];
--rightv[a[s[n]]];
++leftv[a[s[n]]];
s2-=a[s[n]];
if(s2<0)
s2+=n;
s1+=a[s[n]];
if(s1>=n)
s1-=n;
step=1;
}
}
if(step==1)
for(i=1;i<=n;++i)
g<<s[i]<<" ";
else
for(i=1;i<=n;++i)
g<<d[i]<<" ";
g<<"\n";
}
/*int rez2()
{
int m[605][305][305];
m[0][0][0]=1;
for(i=1;i<=n*2-1;++i)
{
f>>a[i];
a[i]%=n;
for(int j=1;j<n;++j)
for(int k=1;k<=n;++k)
{
m[i&1][j][k]=m[i-1&1][j][k];
if(m[i&1][j][k]==0)
{
int p=k-a[i];
if(p<0)
p+=n;
m[i&1][j][k]=m[i-1&1][j-1][p];
}
}
}*/
int main()
{
f>>n;
rez1();
}