Cod sursa(job #2026465)

Utilizator FrequeAlex Iordachescu Freque Data 24 septembrie 2017 14:34:22
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("disjoint.in");
ofstream fout("disjoint.out");

const int NMAX = 100000 + 5;

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

int n, m;
int casa[NMAX];
int root[NMAX];
query q[NMAX];

void read()
{
    fin >> n >> q[1].a >> q[1].b >> q[1].c;

    for (int i = 2; i < n; ++i)
    {
        q[i].a = (q[i - 1].a * i) % n;
        q[i].b = (q[i - 1].b * i) % n;
        q[i].c = (q[i - 1].c * i) % n;
    }

    for (int i = 1; i <= n; ++i)
        root[i] = i;
}

int find_root(int x)
{
    int i;
    for (i = x; i != root[i]; i = root[i]);

    while (x != root[x])
    {
        int y = root[x];
        root[x] = i;
        x = y;
    }

    return i;
}
/*
void unite(int x, int y)
{
    if (rang[x] > rang[y])
    {
        rang[x] += rang[y];
        root[y] = x;
    }
    else
    {
        rang[y] += rang[x];
        root[x] = y;
    }
}
*/
int main()
{
    int cod, x, y;
    read();

    for (int i = n - 1; i >= 1; --i)
    {
        int poz = find_root(q[i].a);
        while (poz <= q[i].b)
        {
            //fac 1
            root[poz] = poz + 1;
            casa[poz] = q[i].c;
            //trec la next
            poz = find_root(poz);
        }
    }

    for (int i = 1; i < n; ++i)
        fout << casa[i] << "\n";

    return 0;
}