Cod sursa(job #3140125)

Utilizator TeodoraMaria123Serban Teodora Maria TeodoraMaria123 Data 3 iulie 2023 22:43:21
Problema Curcubeu Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 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 = (a * i) % n;
        b = (b * i) % n;
        c = (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;
//        cout << pos << " ";
        int x = findNextPos(updates[i].right + 1);
        while(pos <= updates[i].right)
        {
            pos = findNextPos(pos);
            v[pos] = updates[i].no;
            nextPos[pos] = x;
            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;
}