Cod sursa(job #1099464)

Utilizator SchumiDumitru Andrei Georgian Schumi Data 5 februarie 2014 21:08:29
Problema Curcubeu Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>

using namespace std;

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

const int N = 1000005;

int n;
int a[N], b[N], c[N];
int color[N];
int Next[N], changes[N];

void read() {
    f >> n >> a[1] >> b[1] >> c[1];
    
    for (int i = 2; i < n; ++i) {
        a[i] = (1LL * a[i - 1] * i) % n;
        b[i] = (1LL * b[i - 1] * i) % n;
        c[i] = (1LL * c[i - 1] * i) % n;
    }
}

void init() {
    for (int i = 1; i <= n; ++i)
        Next[i] = i;
}

int nextPoz(int start) {
    int nc = 1; //number of changes on the way

    changes[1] = start;
    while (changes[nc] != Next[changes[nc]]) {
        ++nc;
        changes[nc] = Next[changes[nc - 1]];
    }

    for (int i = 1; i <= nc; ++i)
        Next[changes[i]] = changes[nc];

    return Next[start];
}

void solve() {
    init();

    for (int i = n - 1; i > 0; --i) {
        int start = min(a[i], b[i]);
        int end = max(a[i], b[i]);
        
        for (int j = nextPoz(start); j <= end; j = Next[j]) {
            Next[j] = nextPoz(j + 1);
            color[j] = c[i];
        }
    }

    for (int i = 1; i < n; ++i)
        g << color[i] << '\n';
}

int main() {
    read();
    solve();
}