Cod sursa(job #2601136)

Utilizator StanCatalinStanCatalin StanCatalin Data 13 aprilie 2020 20:31:17
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda arfibinesaintratilaasta Marime 2.05 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int dim = 1000005;

struct que
{
    int x,y,z;
};

int n,a,b,c,arb[4*dim],pus[dim];
que querry[dim];

void Update(int nod,int st,int dr, int a,int b,int col)
{
    ///cout << st << " " << dr << " " << a << " " << b << "\n";;
    if (a > b)
        return ;
    if (st == a && dr == b && arb[nod] == 0)
    {
        arb[nod] = col;
        pus[nod] = 1;
        return ;
    }
    if (pus[nod])
    {
        arb[2*nod] = arb[2*nod + 1] = arb[nod];
        pus[2*nod] = pus[2*nod+1] = 1;
        pus[nod] = 0;
    }
    int mid = (st+dr)/2;
    Update(2*nod,  st,    mid, a,             min(b,mid),col);
    Update(2*nod+1,  mid+1, dr,  max(a, mid+1), b,         col);
}

int Querry(int nod,int st,int dr,int poz)
{
    if (st == dr)
        return arb[nod];
    if (pus[nod])
    {
        arb[2*nod] = arb[2*nod + 1] = arb[nod];
        pus[2*nod] = pus[2*nod+1] = 1;
        pus[nod] = 0;
    }
    int mid = (st+dr)/2;
    if (poz <= mid)
    {
        return Querry(2*nod,st,mid, poz);
    }
    else return Querry(2*nod+1, mid+1,dr,poz);
}

int main()
{
    in >> n >> a >> b >> c;
    querry[1] = {a,b,c};
    for (int i=2; i<=n; i++)
    {
        querry[i].x = (querry[i-1].x * i)%n;
        /* if ((querry[i-1].x * i)%n == 0)
         {
             querry[i].x = n;
         }*/
        querry[i].y = (querry[i-1].y * i)%n;
        /* if ((querry[i-1].y * i)%n == 0)
         {
             querry[i].y = n;
         }*/
        querry[i].z = (querry[i-1].z * i)%n;
        /*if ((querry[i-1].z * i)%n == 0)
        {
            querry[i].z = n;
        }*/
    }
    for (int i=n-1; i>=1; i--)
    {
        int st = min(querry[i].x, querry[i].y);
        int dr = max(querry[i].x, querry[i].y);
        ///  cout << st << " " << dr << "\n";
        Update(1,1,n,st,dr,querry[i].z);
    }
    for (int i=1; i<=n-1; i++) out << Querry(1,1,n,i) << "\n";
    return 0;
}