Cod sursa(job #3240323)

Utilizator Botnaru_VictorBotnaru Victor Botnaru_Victor Data 14 august 2024 01:06:15
Problema Curcubeu Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 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++)
    {
        qs[i] = c;
        r.update(min(a, b), max(a, b), i);
        a = (1LL*a*(i+1)) %n;
        b= (1LL*b*(i+1)) %n;
        c = (1LL*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';
    }

}