Cod sursa(job #3240319)

Utilizator Botnaru_VictorBotnaru Victor Botnaru_Victor Data 14 august 2024 01:00:13
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <bits/stdc++.h>
#pragma gcc optimize("O3")
using namespace std;

const int maxn = 1e6+5;

struct Raru{

    vector<int>arb;
    int offset;

    Raru(int n)
    {
        arb.resize(n*4+1,0);
        offset = n;
    }

    void update(int st, int dr, int val)
    {
        for(st+=offset-1, dr+=offset; st<dr; st>>=1, dr>>=1 )
        {
            if(st&1) arb[st++]=val;
            if(dr&1) arb[--dr]=val;
        }
    }

    int query(int poz)
    {
        int ans=0;
        for(poz+=offset-1;poz>0; poz>>=1)
        {
            ans=max(ans, arb[poz]);
        }
        return ans;
    }
};

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


int n;
int qs[maxn];
int a,b,c;

int main()
{
    f>>n>>a>>b>>c;
    Raru r(n);
    for(int i=1;i<n;i++)
    {
        int vala = r.query(a);
        int valb = r.query(b);
        if(vala==0) vala=a;
        else vala=qs[vala];
        if(valb==0) valb=b;
        else valb = qs[valb];
        qs[i] = c;
        r.update(min(vala, valb), max(vala, valb), i);

        cerr<<"here "<<a<<' '<<b<<' '<<c<<'\n';

        a = (a*(i+1)) %n;
        b= (b*(i+1)) %n;
        c = (c*(i+1)) %n;
    }

    for(int i=1;i<n;i++)
    {
        int val = r.query(i);
        if(val==0) val = i;
        else val = qs[val];
        g<<val<<'\n';
    }

}