Cod sursa(job #2462019)

Utilizator StanCatalinStanCatalin StanCatalin Data 26 septembrie 2019 17:52:51
Problema Curcubeu Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream in("curcubeu.in");
ofstream out("curcubeu.out");

const int dim = 1000001;

int n,a,b,c,parent[dim],ans[dim];

struct q
{
    int a,b,c;
};

vector <q> query;

int Find(int x)
{
    if (x == parent[x])
    {
        return x;
    }
    parent[x] = Find(parent[x]);
    return parent[x];
}

int main()
{
    in >> n >> a >> b >> c;
    for (int i=1; i<=n; i++)
    {
        parent[i] = i;
    }
    query.push_back({a,b,c});
    int a_nou,b_nou,c_nou;
    for (int i=2; i<=n-1; i++)
    {
        a_nou = (a*i)%n;
        b_nou = (b*i)%n;
        c_nou = (c*i)%n;
        query.push_back({a_nou,b_nou,c_nou});
        a = a_nou;
        b = b_nou;
        c = c_nou;
    }
    reverse(query.begin(),query.end());

    int st,dr;


    for (int i=0; i<query.size(); i++)
    {
        st = min(query[i].a , query[i].b);
        dr = max(query[i].a , query[i].b);

        for (int j=Find(st); j<=dr; j = Find(j))
        {
            ans[j] = query[i].c;
            parent[j] = j+1;
        }
    }
    for (int i=1; i<=n-1; i++)
    {
        out << ans[i] << "\n";
    }
    return 0;
}