Cod sursa(job #3140135)

Utilizator TeodoraMaria123Serban Teodora Maria TeodoraMaria123 Data 4 iulie 2023 00:02:01
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <bits/stdc++.h>

using namespace std;

#define pb push_back

int n, a, b, c;

struct update
{
    int left, right, no;
};
vector <int> nextPos, v;
vector <update> updates;

int findNextPos(int x)
{
    assert(x <= n);
    if(x == nextPos[x])
        return x;
    return nextPos[x] = findNextPos(nextPos[x]);
}

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

    freopen("curcubeu.in", "r", stdin);
    freopen("curcubeu.out", "w", stdout);

    cin >> n >> a >> b >> c;
    nextPos.resize(n + 1);
    v.resize(n + 1);

    for(int i = 1; i <= n; i ++)
        nextPos[i] = i;

    if(a < b)
        updates.pb({a, b, c});
    else
        updates.pb({b, a, c});

    for(int i = 2; i < n; i ++)
    {
        cin >> a >> b >> c;
        a = (1ll * a * i) % n;
        b = (1ll * b * i) % n;
        c = (1ll * c * i) % n;
        if(a < b)
            updates.pb({a, b, c});
        else
            updates.pb({b, a, c});
    }

    for(int i = n - 2; i >= 0; i --)
    {
        int pos = updates[i].left;
        int x = findNextPos(updates[i].right + 1);
        while(pos <= updates[i].right)
        {
            if(pos == nextPos[pos])
            {
                v[pos] = updates[i].no;
                nextPos[pos] = x;
                pos ++;
            }
            else
                pos = findNextPos(pos);

//            cout << pos << " ";

        }
//        cout << "\n";
    }
//    for(int x : nextPos)
//        cout << x << " ";
//    cout << "\n";

    for(int i = 1; i < n; i++)
        cout << v[i] << "\n";

    return 0;
}