Pagini recente » Borderou de evaluare (job #970346) | Borderou de evaluare (job #353174) | Borderou de evaluare (job #1314812) | Borderou de evaluare (job #1172245) | Cod sursa (job #2501481)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f ("curcubeu.in");
ofstream g ("curcubeu.out");
long long a[1000100], b[1000100], c[1000100],v[1000100],t[1000100], n,h[1000100],poz[1000100];
int calc(int x)
{
int y=x, z=x;
while(t[y]) y=t[y];
while(0!=t[x])
{
z=x;
x=t[x];
t[z]=y;
}
return y;
}
void join(int x, int y)
{
x=calc(x);
y=calc(y);
if(x==y) return ;
if(h[x]<h[y])
{
t[x]=y;
poz[y]=max(poz[y],poz[x]);
}
else if(h[x]>h[y])
{
t[y]=x;
poz[x]=max(poz[y],poz[x]);
}
else
{
t[x]=y;
h[y]++;
poz[y]=max(poz[y],poz[x]);
}
}
int main()
{
f>>n>>a[1]>>b[1]>>c[1];
if(a[1]>b[1]) swap(a[1], b[1]);
h[1]=1;
poz[1]=1;
for(int i=2;i<n;++i)
{
a[i]=(a[i-1]%n*i%n)%n;
b[i]=(b[i-1]%n*i%n)%n;
c[i]=(c[i-1]%n*i%n)%n;
h[i]=1;
poz[i]=i;
if(a[i]>b[i])
swap(a[i], b[i]);
}
poz[n]=n;
long long aux,j;
for(int i=n-1;i>0;--i)
{
j=calc(a[i]);
j=poz[j];
while(j<=b[i])
{
if(v[j]==0)
v[j]=c[i];
join(j, b[i]);
j=calc(++j);
j=poz[j];
}
}
for(int i=1;i<n;++i)
g<<v[i]<<"\n";
return 0;
}