Cod sursa(job #3247383)

Utilizator paull122Paul Ion paull122 Data 7 octombrie 2024 14:57:36
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <bits/stdc++.h>

#define VMAX 50000
#define NMAX 1000000

#define LOG 22
#define INF (long long)(1e9)
#define MOD 1000000007
#define ll long long int

#define ADD 1e9

#define NIL 0




using namespace std;
ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");

struct query
{
    int a,b,c;
} q[NMAX+1];

int dr[NMAX+1],n,res[NMAX+1],st[NMAX+1];

int Parent[NMAX+1];
int Find(int x)
{
    if(x!=Parent[x])
    {
        Parent[x] = Find(Parent[x]);
    }
    return Parent[x];
}

void Unite(int x,int y)
{
    x = Find(x);
    y = Find(y);

    Parent[x]=y;
}
int main()
{
    fin >> n;
    fin >> q[1].a >> q[1].b >> q[1].c;
    for(int i=2;i<n;i++)
    {
        q[i].a = i*1ll*q[i-1].a%n;
        q[i].b = i*1ll*q[i-1].b%n;
        q[i].c = i*1ll*q[i-1].c%n;

        if(q[i].a > q[i].b)
        {
            swap(q[i].a,q[i].b);
        }
    }
    for(int i=1;i<=n;i++)
    {
        Parent[i]=i;
        res[i]=0;
    }
    dr[n]=0;
    for(int i=n-1;i>=1;i--)
    {
        int l = Find(q[i].a);
        int r = Find(q[i].b+1);
        int c = q[i].c;

        while(l<=q[i].b)
        {
            res[l]=c;
            Unite(l,r);
            l = Find(l+1);
        }
    }
    for(int i=1;i<n;i++)
    {
        fout << res[i] << "\n";
    }
}