Cod sursa(job #3361816)

Utilizator nicoleta_iancuIancu Nicoleta nicoleta_iancu Data 28 iulie 2026 18:37:00
Problema Curcubeu Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.4 kb

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");
int n;
struct query {
    int st, dr, color;
    query() :st(-1), dr(-1), color(0) {};
    query(query& ant,int i) {
        int auxSt = (ant.st * i) % n;
        int auxDr = (ant.dr * i) % n;
        this->st = min(auxSt,auxDr);
        this->dr = max(auxSt, auxDr);
        this->color= (ant.color * i) % n;
    }
};
class disjuncte {
    public: 
    vector<int>father;
    vector<int>maxPoz;//pozitia maxima care este colorata pe un anumit interval
    void resize(int n) {
        father.resize(n, -1);
        maxPoz.resize(n);
        for (int i = 0; i < n; ++i) {
            maxPoz[i] = i;
        }
    }
    int getRoot(int nod) {
        if (father[nod] == -1) {
            return nod;
        }
        father[nod] = getRoot(father[nod]);
        return father[nod];
    }
    void combin(int a,int b) {
        a = getRoot(a);
        b = getRoot(b);
        if (a != b) {
            father[b] = a;
            maxPoz[a] = max(maxPoz[a], maxPoz[b]);
        }
    }
};
int main()
{
    int a,b,c;
    fin >> n>>a>>b>>c;
    disjuncte forest;
    forest.resize(n);
    vector<int>colors(n, -1);
    vector<query>q(n-1);
    q[0].st = min(a, b);
    q[0].dr = max(a, b);
    q[0].color = c;
    for (int i = 1; i < n-1; ++i) {
        q[i] = query(q[i - 1], i + 1);
    }
    for (int i = n - 2; i >= 0; --i) {
        int poz = forest.getRoot(q[i].st);
        int startSecv = -1;
        while (poz<=q[i].dr)
        {
            if (colors[poz]==-1) {//le unim cu multimea inceputului secventei
                colors[poz] = q[i].color;
                if (startSecv ==-1) {
                    startSecv = poz;
                }
                else {
                    forest.combin(startSecv, poz);
                }
            }
            else {//sarim peste toate din aceasta multime
                if (startSecv!=-1) {//vrem sa le combinam cu multimea anterioara ca sa sarim mai mult daca mai vine un query (sper)
                    forest.combin(startSecv, poz);
                }
                poz = forest.maxPoz[poz];
            }
            ++poz;
        }

    }
    for (int i = 1; i < n; ++i) {
        fout << colors[i] << "\n";
    }
    return 0;
}
//=^..^=