Cod sursa(job #1345931)

Utilizator tudorv96Tudor Varan tudorv96 Data 17 februarie 2015 22:18:37
Problema Curcubeu Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <vector>
#include <fstream>
#include <queue>
using namespace std;

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

const int N = 1e6 + 5;

int n, a, b, c, k;

bool f[N];

vector <pair <int, int> > vin[N], vout[N];
priority_queue <pair <int, int>, vector <pair <int, int> > > H;

void update(int &a, int &b, int &c) {
    int A = min(a, b), B = max(a, b);
    vin[A].push_back(make_pair (k, c));
    vout[B].push_back(make_pair (k++, c));
}

int main() {
    fin >> n >> a >> b >> c;
    update(a, b, c);
    for (int i = 2; i < n; ++i) {
        a = (1LL * a * i) % n;
        b = (1LL * b * i) % n;
        c = (1LL * c * i) % n;
        update(a, b, c);
    }
    for (int i = 1; i < n; ++i) {
        for (vector <pair <int, int> > :: iterator it = vin[i].begin(); it != vin[i].end(); ++it) {
            f[it -> first] = 1;
            H.push(*it);
        }
        while (H.size() && !f[H.top().first])
            H.pop();
        if (H.size())
            fout << H.top().second << "\n";
        else
            fout << "0\n";
        for (vector <pair <int, int> > :: iterator it = vout[i].begin(); it != vout[i].end(); ++it)
            f[it -> first] = 0;
    }
}