제출 #566119

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
566119		piOOE	ICC (CEOI16_icc)	C++17	100 / 100	108 ms	652 KiB

icc

#include "icc.h"
#include <bits/stdc++.h>

using namespace std;

#define all(x) begin(x), end(x)
#define sz(x) ((int)size(x))
#define trace(x) cout << #x << ": " << (x) << endl;

typedef long long ll;

int ask(vector<int> a, vector<int> b) {
    for (int &x: a) ++x;
    for (int &y: b) ++y;
    return query(sz(a), sz(b), a.data(), b.data());
}

vector<int> p;

int get(int a) {
    return a == p[a] ? a : p[a] = get(p[a]);
}

bool mrg(int a, int b) {
    a = get(a), b = get(b);
    if (a == b) {
        return false;
    }
    p[b] = a;
    return true;
}

void run(int n) {
    p.resize(n);
    iota(all(p), 0);
    for (int cnt = 1; cnt < n; ++cnt) {
        vector<int> v;
        for (int i = 0; i < n; ++i) {
            if (p[i] == i) v.push_back(i);
        }
        assert(sz(p) > 1);
        vector<vector<int>> f, s;
        f.emplace_back(), s.emplace_back();
        for (int i = 0; i < sz(v); ++i) {
            if (i & 1) s.back().push_back(v[i]);
            else f.back().push_back(v[i]);
        }
        map<int, vector<int>> lst;
        for (auto a: f.back())
            lst[a] = s.back();
        for (auto a: s.back())
            lst[a] = f.back();
        while (true) {
            vector<int> a, b;
            for (auto &x: f) {
                for (int y: x) {
                    for (int i = 0; i < n; ++i) {
                        if (get(i) == y) a.push_back(i);
                    }
                }
            }
            for (auto &x: s) {
                for (int y: x) {
                    for (int i = 0; i < n; ++i) {
                        if (get(i) == y) b.push_back(i);
                    }
                }
            }
            if (ask(a, b)) break;
            lst.clear();
            vector<vector<int>> ff, ss;
            for (auto &x: f) {
                ff.emplace_back();
                ss.emplace_back();
                for (int i = 0; i < sz(x); ++i) {
                    if (i & 1) ss.back().push_back(x[i]);
                    else ff.back().push_back(x[i]);
                }
                if (ss.back().empty()) {
                    ss.pop_back();
                    continue;
                }
                if (ff.back().empty()) {
                    ff.pop_back();
                    continue;
                }
                for (auto aa: ff.back())
                    lst[aa] = ss.back();
                for (auto aa: ss.back())
                    lst[aa] = ff.back();
            }
            for (auto &x: s) {
                ff.emplace_back();
                ss.emplace_back();
                for (int i = 0; i < sz(x); ++i) {
                    if (i & 1) ss.back().push_back(x[i]);
                    else ff.back().push_back(x[i]);
                }
                if (ss.back().empty()) {
                    ss.pop_back();
                    continue;
                }
                if (ff.back().empty()) {
                    ff.pop_back();
                    continue;
                }
                for (auto aa: ff.back())
                    lst[aa] = ss.back();
                for (auto aa: ss.back())
                    lst[aa] = ff.back();
            }
            swap(f, ff);
            swap(s, ss);
        }
        {
            vector<int> a, b;
            for (auto &x: f) {
                for (int y: x) {
                    for (int i = 0; i < n; ++i) {
                        if (get(i) == y) a.push_back(i);
                    }
                }
            }
            for (auto &x: s) {
                for (int y: x) {
                    for (int i = 0; i < n; ++i) {
                        if (get(i) == y) b.push_back(i);
                    }
                }
            }
            int l = 0, r = sz(b);
            while (l + 1 < r) {
                int m = (l + r) >> 1;
                vector<int> c;
                for (int i = l; i < m; ++i) {
                    c.push_back(b[i]);
                }
                if (ask(a, c)) r = m;
                else l = m;
            }
            int v1 = b[l];
            {
                auto xx = lst[get(v1)];
                a.clear();
                for (int y: xx) {
                    for (int i = 0; i < n; ++i) {
                        if (get(i) == y) a.push_back(i);
                    }
                }
            }
            l = 0, r = sz(a);
            while (l + 1 < r) {
                int m = (l + r) >> 1;
                vector<int> c;
                for (int i = l; i < m; ++i) {
                    c.push_back(a[i]);
                }
                if (ask({v1}, c)) r = m;
                else l = m;
            }
            int v2 = a[l];
            setRoad(v1 + 1, v2 + 1);
            mrg(v1, v2);
        }
    }
}

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