oj.uz

Submission #528344

# Submission time Handle Problem Language Result Execution time Memory
528344 2022-02-20T05:25:05 Z KoD ICC (CEOI16_icc) C++17
100 / 100
 155 ms 588 KB 
#include "icc.h"
#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

struct UnionFind {
    vector<int> par;
    UnionFind(const int n) : par(n, -1) {}
    int find(const int u) {
        return par[u] < 0 ? u : par[u] = find(par[u]);
    }
    void merge(int x, int y) {
        x = find(x), y = find(y);
        if (x != y) par[y] = x;
    }
};

int ask(const vector<int>& a, const vector<int>& b) {
    if (a.empty() or b.empty()) return 0;
    static int id_a[100], id_b[100];
    int size_a = 0, size_b = 0;
    for (const int x : a) id_a[size_a++] = x + 1;
    for (const int x : b) id_b[size_b++] = x + 1;
    return query(size_a, size_b, id_a, id_b);
}

void run(int N) {
    std::default_random_engine gen(998244353);
    UnionFind dsu(N);
    for (int step = 0; step < N - 1; ++step) {
        vector<int> roots;
        for (int i = 0; i < N; ++i) {
            if (dsu.find(i) == i) {
                roots.push_back(i);
            }
        }
        vector<int> perm(roots.size());
        std::iota(perm.begin(), perm.end(), 0);
        std::shuffle(perm.begin(), perm.end(), gen);
        vector<int> value(N);
        for (int i = 0; i < (int)roots.size(); ++i) {
            value[roots[i]] = perm[i];
        }
        vector<int> left, right;
        for (int d = 0; d < 7; ++d) {
            left.clear();
            right.clear();
            for (int i = 0; i < N; ++i) {
                if (value[dsu.find(i)] >> d & 1) {
                    left.push_back(i);
                } else {
                    right.push_back(i);
                }
            }
            if (ask(left, right)) {
                break;
            }
        }
        while (left.size() > 1 or right.size() > 1) {
            const int n = left.size();
            const int m = right.size();
            vector<int> l1(left.begin(), left.begin() + n / 2), l2(left.begin() + n / 2, left.end());
            vector<int> r1(right.begin(), right.begin() + m / 2), r2(right.begin() + m / 2, right.end());
            left = ask(l1, right) ? l1 : l2;
            right = ask(left, r1) ? r1 : r2;
        }
        const int a = left[0];
        const int b = right[0];
        setRoad(a + 1, b + 1);
        dsu.merge(a, b);
    }
}

#ifdef __APPLE__

int query(int size_a, int size_b, int a[], int b[]) {
    for (int i = 0; i < size_a; ++i) std::cout << a[i] << ' ';
    std::cout << '|';
    for (int i = 0; i < size_b; ++i) std::cout << ' ' << b[i];
    std::cout << std::endl;
    int ret;
    std::cin >> ret;
    return ret;
}

void setRoad(int a, int b) {
    std::cout << a << ' ' << b << '\n';
}

int main() {
    int N;
    std::cin >> N;
    run(N);
}

#endif

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 464 KB Ok! 98 queries used.
2 Correct 5 ms 492 KB Ok! 96 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 472 KB Ok! 530 queries used.
2 Correct 38 ms 464 KB Ok! 672 queries used.
3 Correct 39 ms 472 KB Ok! 661 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 484 KB Ok! 1460 queries used.
2 Correct 132 ms 492 KB Ok! 1638 queries used.
3 Correct 152 ms 496 KB Ok! 1584 queries used.
4 Correct 135 ms 476 KB Ok! 1514 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 500 KB Ok! 1591 queries used.
2 Correct 141 ms 484 KB Ok! 1579 queries used.
3 Correct 150 ms 496 KB Ok! 1614 queries used.
4 Correct 117 ms 588 KB Ok! 1529 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 480 KB Ok! 1618 queries used.
2 Correct 125 ms 496 KB Ok! 1613 queries used.
3 Correct 124 ms 480 KB Ok! 1624 queries used.
4 Correct 139 ms 492 KB Ok! 1610 queries used.
5 Correct 155 ms 492 KB Ok! 1519 queries used.
6 Correct 133 ms 480 KB Ok! 1551 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 480 KB Ok! 1614 queries used.
2 Correct 140 ms 488 KB Ok! 1619 queries used.