oj.uz

Submission #676335

# Submission time Handle Problem Language Result Execution time Memory
676335 2022-12-30T11:37:14 Z finn__ Zamjene (COCI16_zamjene) C++17
14 / 140
 6000 ms 182412 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 340 KB Output is correct
2 Incorrect 109 ms 304 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 905 ms 432 KB Output is correct
2 Correct 1423 ms 468 KB Output is correct
3 Correct 1452 ms 468 KB Output is correct

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6037 ms 2028 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6046 ms 17736 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6065 ms 89164 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6059 ms 182412 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6055 ms 177936 KB Time limit exceeded
2 Halted 0 ms 0 KB -