Cod sursa(job #1346176)

Utilizator tudorv96Tudor Varan tudorv96 Data 18 februarie 2015 07:49:51
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
using namespace std;

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

const int N = 4e6 + 5;

int n, a, b, c, Next[N], v[N];

struct muchie {
    int a, b, c;
} mc[N];

int find(int x) {
    if (Next[x] != x)
        Next[x] = find(Next[x]);
    return Next[x];
}

void unite(int x, int y) {
    Next[x] = find(y);
}

int main() {
    fin >> n >> a >> b >> c;
    for (int i = 1; i < n; ++i) {
        Next[i] = i;
        mc[i].a = min(a, b);
        mc[i].b = max(a, b);
        mc[i].c = c;
        a = (1LL * a * (i + 1)) % n;
        b = (1LL * b * (i + 1)) % n;
        c = (1LL * c * (i + 1)) % n;
    }
    for (int i = n - 1; i; --i) {
        for (int j = mc[i].a; j <= mc[i].b; ++j)
            if (Next[j] != j) {
                j = Next[j];
                continue;
            }
            else
                if (!v[j]) {
                    v[j] = mc[i].c;
                    unite(j, mc[i].b);
                }
    }
    for (int i = 1; i < n; ++i)
        fout << v[i] << "\n";
}