Submission #676335

#	Time	Username	Problem	Language	Result	Execution time	Memory
676335		finn__	Zamjene (COCI16_zamjene)	C++17	14 / 140	6065 ms	182412 KiB

zamjene

#include <bits/stdc++.h>
using namespace std;

#define MOD (__uint128_t)((1ULL << 61) - 1)
#define BASE (__uint128_t)1000000009

template <typename T>
T mod_exp(T x, T y, T m)
{
    T u = 1, v = x;

    while (y)
    {
        if (y & 1)
            u = (u * v) % m;
        v = (v * v) % m;
        y >>= 1;
    }

    return u;
}

template <typename T>
T mod_inv(T x, T m)
{
    return mod_exp(x, m - 2, m);
}

int main()
{
    size_t n, q;
    cin >> n >> q;

    vector<uint64_t> y(n);
    for (uint64_t &x : y)
        cin >> x;
    vector<uint64_t> z(y.begin(), y.end());
    sort(z.begin(), z.end());

    vector<size_t> comp(n);
    vector<set<size_t>> comp_set(n);
    for (size_t i = 0; i < n; i++)
    {
        comp[i] = i;
        comp_set[i] = {i};
    }

    vector<uint64_t> h1(n), h2(n);
    for (size_t i = 0; i < n; i++)
    {
        h1[i] = y[i] + BASE;
        h2[i] = z[i] + BASE;
    }

    set<size_t> cant_sort;
    for (size_t i = 0; i < n; i++)
        if (h1[i] != h2[i])
            cant_sort.insert(i);

    for (size_t i = 0; i < q; i++)
    {
        int t;
        cin >> t;

        switch (t)
        {
        case 1:
        {
            uint64_t a, b;
            cin >> a >> b;
            a--, b--;

            h1[comp[a]] = (h1[comp[a]] * mod_inv(y[a] + BASE, MOD)) % MOD;
            h1[comp[a]] = (h1[comp[a]] * (y[b] + BASE)) % MOD;
            h1[comp[b]] = (h1[comp[b]] * mod_inv(y[b] + BASE, MOD)) % MOD;
            h1[comp[b]] = (h1[comp[b]] * (y[a] + BASE)) % MOD;

            cant_sort.erase(comp[a]);
            cant_sort.erase(comp[b]);
            if (h1[comp[a]] != h2[comp[a]])
                cant_sort.insert(comp[a]);
            if (h1[comp[b]] != h2[comp[b]])
                cant_sort.insert(comp[b]);

            swap(y[a], y[b]);
            break;
        }
        case 2:
        {
            uint64_t a, b;
            cin >> a >> b;
            a--, b--;

            if (comp_set[comp[a]].size() < comp_set[comp[b]].size())
                swap(a, b);
            comp_set[comp[a]].insert(comp_set[comp[b]].begin(), comp_set[comp[b]].end());
            size_t const c = comp[b];
            for (size_t const &j : comp_set[c])
                comp[j] = comp[a];
            comp_set[c].clear();

            h1[comp[a]] = (h1[comp[a]] * (__uint128_t)h1[c]) % MOD;
            h2[comp[a]] = (h2[comp[a]] * (__uint128_t)h2[c]) % MOD;

            cant_sort.erase(comp[a]);
            cant_sort.erase(c);

            if (h1[comp[a]] != h2[comp[a]])
                cant_sort.insert(comp[a]);
            break;
        }
        case 3:
        {
            cout << (cant_sort.empty() ? "DA" : "NE") << '\n';
            break;
        }
        case 4:
        {
            uint64_t num_pairs = 0;
            for (size_t i = 0; i < n; i++)
                if (h1[comp[i]] != h2[comp[i]])
                    for (size_t j = i + 1; j < n; j++)
                        if (h1[comp[j]] != h2[comp[j]] &&
                            (h1[comp[i]] * (__uint128_t)h1[comp[j]]) % MOD == (h2[comp[i]] * (__uint128_t)h2[comp[j]]) % MOD)
                            num_pairs++;
            cout << num_pairs << '\n';
            break;
        }
        }
    }
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 14 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14