Submission #1279125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279125		Lithanium	ICC (CEOI16_icc)	C++20	100 / 100	82 ms	620 KiB

icc

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

static int dsu[105];

static int find(int n) {
    if (dsu[n] == n) return n;
    return dsu[n] = find(dsu[n]);
}

static void merge(int a, int b) {
    dsu[find(a)] = find(b);
}

int ask(vector<int> a, vector<int> b) {
    return query(a.size(), b.size(), a.data(), b.data());
}

void run(int N) {
    for (int i = 1; i <= N; i ++) dsu[i] = i;

    for (int it = 1; it < N; it ++) {
        // get the stuff that are still valid
        vector<int> cc;
        for (int i = 1; i <= N; i ++) if (find(i) == i) cc.push_back(i);
        // use hamming code to find two different groups
        vector<int> a, b;
        for (int i = 0; i < 7; i ++) {
            // which binary digit
            set<int> A, B;
            for (int j = 0; j < cc.size(); j ++) {
                if (j&(1 << i)) A.insert(cc[j]);
                else B.insert(cc[j]);
            }
            a.clear();
            b.clear();
            for (int j = 1; j <= N; j ++) {
                if (A.count(find(j))) a.push_back(j);
                if (B.count(find(j))) b.push_back(j);
            }
            if (ask(a, b)) break;
        }
        // binary search to find which two things have an edge
        // binary search on a first
        int low = 0, high = a.size()-1;
        while (high > low) {
            int mid = (low + high)/2;
            vector<int> t;
            for (int i = low; i <= mid; i ++) t.push_back(a[i]);
            if (ask(t, b)) high = mid;
            else low = mid+1;
        }
        a = {a[low]};
        // binary search on b next
        low = 0, high = b.size()-1;
        while (high > low) {
            int mid = (low + high)/2;
            vector<int> t;
            for (int i = low; i <= mid; i ++) t.push_back(b[i]);
            if (ask(a, t)) high = mid;
            else low = mid+1;
        }
        setRoad(a[0], b[low]);
        merge(a[0], b[low]);
    }
}

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