Cod sursa(job #2708123)

Utilizator CiboAndreiAndrei Cibo CiboAndrei Data 18 februarie 2021 12:45:41
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <bits/stdc++.h>

using namespace std;

//#define f cin
//#define g cout
//ifstream f("data.in");
//ofstream g("data.out");
ifstream f("curcubeu.in");
ofstream g("curcubeu.out");

const int dim = 1e6 + 2;
const short int mod = 1e9 + 7;

long long n, a, b, c;
int sol[dim];

struct str{
    long long x, y, z;
};
vector <str> v;

vector <int> inv;

void init(){
    f >> n >> a >> b >> c;
}

void print_sol(){
    for(int i = 1; i < n; ++i)
        g << sol[i] << '\n';
}

int caubin(int x){
    int st = 1, dr = inv.size() - 1, m;

    while(st <= dr){
        m = (st + dr) / 2;

        if(inv[m] < x)
            st = m + 1;
        else dr = m - 1;
    }

    return dr;
}

void solve(){
    int i, j;

    for(i = 1; i < n; ++i){
        a = (a*i) % n;
        b = (b*i) % n;
        c = (c*i) % n;

        if(a < b){
            v.push_back({a, b, c});
        } else {
            v.push_back({b, a, c});
        }
    }

    for(i = v[n - 2].x; i <= v[n - 2].y; ++i)
        sol[i] = v[n - 2].z;
    inv.push_back(0);
    inv.push_back(v[n - 2].x);
    inv.push_back(v[n - 2].y);

    for(i = n - 3; i >= 0; --i){
        a = v[i].x; b = v[i].y; c = v[i].z;

        int pozst = caubin(a);
        int pozdr = caubin(b);

        if(pozst == pozdr && pozst % 2 == 1){
            continue;
        } else if(pozdr == 0 || pozst == inv.size() - 1){
            for(j = pozst; j <= pozdr; ++j)
                sol[j] = c;
            inv.insert(inv.begin() + pozst + 1, a);
            inv.insert(inv.begin() + pozst + 2, b);
        } else {
            int start, finish;

            if(pozst % 2 == 1){
                start = inv[++pozst];
            } else {
                start = a - 1;
            }

            if(pozdr % 2 == 1){
                finish = inv[pozdr];
            } else {
                finish = b + 1;
            }

            for(; pozst <= pozdr; pozst += 2){
                for(j = start + 1; j < inv[pozst + 1] && j < finish; ++j){
                    sol[j] = c;
                }

                if(pozst + 2 < inv.size())
                    start = inv[pozst + 2];
            }

            inv.erase(inv.begin() + pozst + 1, inv.begin() + pozdr);
            inv.insert(inv.begin() + pozst + 1, a);
            inv.insert(inv.begin() + pozst + 2, b);
        }
    }
}

int main(){
    init();
    solve();
    print_sol();

    return 0;
}