Cod sursa(job #2134178)

Utilizator MarinPeptenaruMarin Vasile Peptenaru MarinPeptenaru Data 17 februarie 2018 18:23:12
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("curcubeu.in");
ofstream out("curcubeu.out");
const int nx=1000002;
long long n,v[nx],urm[nx],a[nx],b[nx],c[nx];
int main()
{
    in>>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;
    }
    for(int i=n-1; i; i--) /// fac operatiile in ordine inversa ca sa nu trebuiasca sa modific valoarea aceleasi case de mai multe ori
    {
        int st=min(a[i],b[i]);
        int dr=max(a[i],b[i]);
        int poz=st;
        while(poz<=dr)
        {
            if(v[poz]) /// daca aceasta casa este deja vizitata
                poz=urm[poz];  /// ma mut pe cea care se afla imediat in afara intervalului parcurs atunci cand am vizitat-o
            else
            {
                v[poz]=c[i];
                urm[poz]=dr+1; /// dr + 1, adica imedita in afara intervalului pe care il parcurg acum
                poz++; /// trec la urmatoarea casa
            }
        }
    }
    for(int i=1; i<n; i++)
        out<<v[i]<<'\n';
    return 0;
}