Cod sursa(job #972615)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 12 iulie 2013 11:31:59
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

const int MAX_N = 1000002;

typedef struct interval {
    int l, r, t, c;
};

int N;
int a[MAX_N];
long long int A, B, C;
interval T;
vector < interval > v[MAX_N];
queue < interval > Q;
stack < interval > st;

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

    f >> N >> A >> B >> C;
    T.l = min(A, B), T.r = max(A, B), T.c = C, T.t = 1;
    v[T.l].push_back(T);
    for(int i = 2; i < N; ++i) {
        A = ((long long) A * i) % N;
        B = ((long long) B * i) % N;
        C = ((long long) C * i) % N;
        T.l = min(A, B), T.r = max(A, B), T.c = C, T.t = i;
        v[T.l].push_back(T);
    }

    for(int i = 1; i < N; ++i) {
        while(!st.empty() && st.top().r < i)
            st.pop();
        int ok = 1;
        while(ok && !Q.empty()) {
            T = Q.front();
            Q.pop();
            if(st.empty() || (T.r >= i && T.t >= st.top().t))
                st.push(T);
            else ok = 0;
        }

        for(size_t j = 0; j < v[i].size(); ++j)
            if(st.empty() || v[i][j].t >= st.top().t)
                st.push(v[i][j]);
            else Q.push(v[i][j]);
        if(!st.empty())
            a[i] = st.top().c;
    }

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

    f.close();
    g.close();

    return 0;
}