Cod sursa(job #2683940)

Utilizator petrisorvmyVamanu Petru Gabriel petrisorvmy Data 12 decembrie 2020 11:32:50
Problema Curcubeu Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <bits/stdc++.h>
#define fast ios_base :: sync_with_stdio(0); cin.tie(0);
#pragma GCC optimize("O3")
#define FILE_NAME "curcubeu"
#define NMAX 1000000 + 100
#define vs nod<<1
#define vd nod<<1|1
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> llp;
typedef pair<ld,ld> pct;

const ll inf = 1LL << 60;
const ll mod = 1e9 + 7;
const ld eps = 1e-9;

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

inline void add(ll &a , ll b)
{
    a += b;
    a %= mod;
}

inline void sub(ll &a, ll b)
{
    a = (a - b + mod) % mod;
}
ll n, a[NMAX], b[NMAX], c[NMAX], nxt[NMAX], sol[NMAX];
inline int getnxt(int nod)
{
    int root = nod;
    while(nxt[root] != root)
        root = nxt[root];
    while(nod != nxt[nod])
    {
        int urm = nxt[nod];
        nxt[nod] = root;
        nod = urm;
    }
    return root;
}
int main()
{
    f >> n >> a[1] >> b[1] >> c[1];
    for(int i = 2; i < n; ++i)
    {
        nxt[i] = i;
        a[i] = (i * a[i - 1]) % n;
        b[i] = (i * b[i - 1]) % n;
        c[i] = (i * c[i - 1]) % n;
    }

    for(int q = n - 1; q >= 1; --q)
    {
        int i = min(a[q], b[q]);
        int j = max(a[q], b[q]);
        for(; i <= j; ++i)
        {
            if(sol[i] == 0)
            {
                sol[i] = c[q];
                nxt[i] = getnxt(j);
            }
            else{
                i = nxt[i];
            }
        }
    }
    for(int i = 1; i < n; ++i)
        g << sol[i] << '\n';
    f.close();
    g.close();
    return 0;
}