제출 #137837

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
137837		darkkcyan	ICC (CEOI16_icc)	C++14	61 / 100	218 ms	632 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
using namespace std::placeholders;

#define llong long long 
#define xx first
#define yy second
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#define all(x) x.begin(), x.end()
#define rand __rand
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());  // or mt19937_64
template<class T = int> T rand(T range = numeric_limits<T>::max()) {
    return (T)(rng() % range);
}

template<class container>
int query(const container& a, const container& b) {
    int cpy_a[len(a)], cpy_b[len(b)];
    copy(a.begin(), a.end(), cpy_a);
    copy(b.begin(), b.end(), cpy_b);
    return query(len(a), len(b), cpy_a, cpy_b);
}

#define maxn 111
int set_head[maxn];
list<int> data[maxn];
int find_set(int u) { return u == set_head[u] ? u : set_head[u] = find_set(set_head[u]); }
void join(int u, int v) {
    u = find_set(u);
    v = find_set(v);
    if (u == v) return ;
    if (rand(2)) swap(u, v);
    set_head[u] = v;
    data[v].splice(data[v].end(), data[u]);  // this is O(1)
}

template<class container>
vector<int> get_all_members(const container& a) {
    vector<int> ans;
    for (auto i: a) {
        copy(data[i].begin(), data[i].end(), back_inserter(ans));
    }
    return ans;
}

tuple<vector<int>, vector<int>> random_split(vector<int> a) {
    random_shuffle(a.begin(), a.end(), rand<int>);
    auto mid = a.begin() + len(a) / 2;
    return {vector<int>(a.begin(), mid), vector<int>(mid, a.end())};
}

void run(int n) {
    rep1(i, n) {
        set_head[i] = i;
        data[i].assign(1, i);
    }

    int n_query = 0;
    rep(edge_num, n - 1) {
        vector<int> head;
        rep1(i, n) 
            if (set_head[i] == i) head.push_back(i);

        vector<int> u, v;
        do {
            tie(u, v) = random_split(head);
            u = get_all_members(u);
            v = get_all_members(v);
            ++n_query;
        } while (query(u, v) == 0);

        vector<int> left, right;

        while (len(u) > 1) {
            tie(left, right) = random_split(u);
            ++n_query;
            if (query(left, v) == 1) u = move(left);
            else u = move(right);
        }

        while (len(v) > 1) {
            tie(left, right) = random_split(v);
            ++n_query;
            if (query(u, left) == 1) v = move(left);
            else v = move(right);
        }

        int a = u[0], b = v[0];
        setRoad(a, b);
        join(a, b);
        // clog << edge_num << ' ' << a << ' ' << b <<  ' ' << n_query << endl;
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 0 / 29
• Subtask 6: 0 / 10