제출 #1149055

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149055		anmattroi	ICC (CEOI16_icc)	C++17	100 / 100	84 ms	624 KiB

icc

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

bool ask(vector<int> X, vector<int> Y) {
    return query(X.size(), Y.size(), X.data(), Y.data());
}

int N;

vector<vector<int> > components;

inline constexpr int bit(const int &x, const int &i) {return (x>>i&1);}


int calc_fork() {
    int mask = 0;
    int sz = components.size();
    int P = __lg(sz-1);
    for (int o = 0; o <= P; o++) {
        vector<int> JOI, KOI;
        for (int i = 0; i < sz; i++)
            if (bit(i,o)) for (int z : components[i]) JOI.emplace_back(z);
            else for (int z : components[i]) KOI.emplace_back(z);

        mask += ((ask(JOI, KOI)) << o);
    }
    return mask;
}

void solve() {
    int mask = calc_fork();
    int A = 0, B = 0;
    int P = __lg(mask);
    int sz = components.size();
    assert(bit(mask, P));
    B += (1<<P);
    for (int o = 0; o <= __lg(sz-1); o++) {
        if (o == P) continue;
        if (mask>>o&1) {
            vector<int> BAOI, BOI;
            for (int i = 0; i < sz; i++) {
                if (!bit(i, o) && !bit(i, P)) for (int z : components[i]) BAOI.emplace_back(z);
                if (bit(i, o) && bit(i, P)) for (int z : components[i]) BOI.emplace_back(z);
            }

            if (ask(BAOI, BOI)) B += (1<<o);
            else A += (1<<o);
        } else {
            vector<int> IMO, IOI;
            for (int i = 0; i < sz; i++) {
                if (!bit(i, o) && !bit(i, P)) for (int z : components[i]) IMO.emplace_back(z);
                if (!bit(i, o) && bit(i, P)) for (int z : components[i]) IOI.emplace_back(z);
            }
            if (!ask(IMO, IOI)) {
                A += (1<<o);
                B += (1<<o);
            }
        }
    }
    vector<int> Dubious = components[A], Furious = components[B];
    int lo = -1, hi = Furious.size()-1;
    while (hi - lo > 1) {
        int mid = (lo + hi) >> 1;

        if (ask(Dubious, vector<int>(Furious.begin(), Furious.begin()+mid+1))) hi = mid;
        else lo = mid;
    }
    int Totally_it_bro = Furious[hi];
    lo = -1, hi = Dubious.size()-1;
    while (hi - lo > 1) {
        int mid = (lo + hi) >> 1;

        if (ask(vector<int>(Dubious.begin(), Dubious.begin()+mid+1), Furious)) hi = mid;
        else lo = mid;
    }
    int You_got_it = Dubious[hi];
    setRoad(Totally_it_bro, You_got_it);
    for (int i : Furious) Dubious.emplace_back(i);
    components[A] = Dubious;
    components.erase(components.begin() + B);
}

void run(int n) {
    components.clear(); components.shrink_to_fit();
    N = n;
    for (int i = 1; i <= n; i++) components.push_back({i});
    for (int i = 1; i < n; i++) solve();
}

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