제출 #528344

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
528344		KoD	ICC (CEOI16_icc)	C++17	100 / 100	155 ms	588 KiB

icc

#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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10