Pagini recente » Cod sursa (job #1661865) | Cod sursa (job #283100) | Cod sursa (job #2789205) | Cod sursa (job #1590103) | Cod sursa (job #3266625)
#include<fstream>
#include<vector>
#include<map>
#pragma GCC optimize("O3")
std::ifstream fin("curcubeu.in");
std::ofstream fout("curcubeu.out");
const int NMAX=1000005;
int n, a, b, c;
int t[NMAX], cnt[NMAX], colors[NMAX];
std::map<int, int>lims;
struct steps{
int a, b, c;
}v[NMAX];
void read()
{
fin>>n>>a>>b>>c;
std::fill(cnt, cnt+n+1, 1);
//t=std::vector<int>(n, 0);
//cnt=std::vector<int>(n, 1);
//colors=std::vector<int>(n, 0);
// v=std::vector<steps>(n);
v[1]={a, b, c};
const int mod=n;
for(int i=2; i<n; ++i)
{
int A=(1LL*v[i-1].a*i)%mod;
int B=(1LL*v[i-1].b*i)%mod;
int C=(1LL*v[i-1].c*i)%mod;
v[i]={A, B, C};
}
}
inline int root(int x)
{
if(!t[x])
return x;
t[x]=root(t[x]);
return t[x];
}
inline void unite(int x, int y)
{
int rx=root(x), ry=root(y);
if(rx==ry)
return;
if(cnt[rx]>=cnt[ry])
{
cnt[rx]+=cnt[ry];
t[ry]=rx;
return;
}
cnt[ry]+=cnt[rx];
t[rx]=ry;
}
void solve()
{
for(int step=n-1; step; --step)
{
int A=v[step].a, B=v[step].b, C=v[step].c;
//int A=a, B=b, C=c;
if(A>B)
std::swap(A, B);
int start=-1, r=-1;
for(int pos=A; pos<=B; ++pos)
{
if(colors[pos]==0)
{
start=pos;
colors[start]=C;
break;
}
else
pos=lims[root(pos)];
}
if(start==-1)
continue;
for(int pos=start+1; pos<=B; ++pos)
{
if(colors[pos]==0)
{
colors[pos]=C;
unite(start, pos);
r=pos;
}
else
pos=lims[root(pos)];
}
lims[start]=r;
}
for(int i=1; i<=n-1; ++i)
fout<<colors[i]<<'\n';
}
int main()
{
read();
solve();
return 0;
}