Cod sursa(job #2004254)

Utilizator Mircea_DonciuDonciu Mircea Mircea_Donciu Data 25 iulie 2017 13:36:59
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");

int n, A[1000010], B[1000010], C[1000010], T[1000010], Next[1000010], Sol[1000010];

int main()
{
    fin >> n >> A[1] >> B[1] >> C[1];
    if (A[1] > B[1]) A[1] ^= B[1] ^= A[1] ^= B[1];
    Next[1] = 2;
    for (int i = 2; i < n; i ++)
    {
        A[i] = (1LL * A[i - 1] * i) % n;
        B[i] = (1LL * B[i - 1] * i) % n;
        if (A[i] > B[i]) A[i] ^= B[i] ^= A[i] ^= B[i];
        C[i] = (1LL * C[i - 1] * i) % n;
        Next[i] = i + 1;
    }

    for (int i = n - 1; i >= 1; i --)
    {
        int j1 = A[i];
        int j2 = B[i];
        while (j1 <= j2)
        {
            if (T[j1] > i)
            {
                j1 = Next[T[j1]];
            }
            else
            {
                Sol[j1] = C[i];
                T[j1] = i;
                Next[i] = j1 + 1;
                j1 ++;
            }
        }
    }

    for (int i = 1; i < n; i ++) fout << Sol[i] << '\n';
    fout.close();
    return 0;
}