Cod sursa(job #2601127)

Utilizator StanCatalinStanCatalin StanCatalin Data 13 aprilie 2020 20:15:10
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda arfibinesaintratilaasta Marime 1.67 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];
que querry[dim];

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

int Querry(int nod,int st,int dr,int poz)
{
    if (st == dr) return arb[nod];
    if (arb[nod]) return arb[nod];
    int mid = (st+dr)/2;
    if (poz <= (st+dr)/2) Querry(2*nod , st, (st+dr)/2,poz);
    else if (poz > (st+dr)/2) Querry(2*nod + 1 , (st+dr)/2 + 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;
}