Cod sursa(job #1345116)

Utilizator tudorv96Tudor Varan tudorv96 Data 17 februarie 2015 11:56:48
Problema Curcubeu Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <fstream>
#include <iostream>
using namespace std;

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

const int N = 4e6 + 5;

int n, a, b, c, A[N];

int query(int node, int lt, int rt, int &q) {
    if (A[node] != -1)
        return A[node];
    if (lt == rt)
        return 0;
    if (q <= (lt + rt) >> 1)
        return query((node << 1), lt, (lt + rt) >> 1, q);
    else
        return query((node << 1) + 1, ((lt + rt) >> 1) + 1, rt, q);
}

void update(int node, int lt, int rt, int lo, int hi, int &v) {
    //cout << node << " " << lt << " " << rt << " " << lo << " " << hi << " " << v << "\n";
    if (A[node] != -1 && lt != rt) {
        A[node << 1] = A[(node << 1) + 1] = A[node];
        A[node] = -1;
    }
    if (lo <= lt && rt <= hi) {
        A[node] = v;
        return;
    }
    if (hi < lt || rt < lo)
        return;
    if (lo <= ((lt + rt) >> 1))
        update(node << 1, lt, (lt + rt) >> 1, lo, hi, v);
    if (hi > ((lt + rt) >> 1))
        update((node << 1) + 1, ((lt + rt) >> 1) + 1, rt, lo, hi, v);
    if (A[node << 1] == A[(node << 1) + 1]) {
        A[node] = A[node << 1];
        A[node << 1] = A[(node << 1) + 1] = -1;
    }
}

int main() {
    fin >> n >> a >> b >> c;
    for (int i = 0; i < N; ++i)
        A[i] = -1;
    update(1, 1, n - 1, min(a, b), max(a, b), c);
    //cout << "\n";
    for (int i = 2; i < n; ++i) {
        a = (a * i) % n;
        b = (b * i) % n;
        c = (c * i) % n;
        update(1, 1, n - 1, min(a, b), max(a, b), c);
        /*cout << "\n";
        for (int i = 1; i < n; ++i)
            fout << query(1, 1, n - 1, i) << " ";
        fout << "\n";*/
    }
    for (int i = 1; i < n; ++i)
        fout << query(1, 1, n - 1, i) << "\n";
}