Cod sursa(job #3266625)

Utilizator MegaCoderMinoiu Teodor Mihai MegaCoder Data 9 ianuarie 2025 16:54:02
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.91 kb
#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;
}