Submission #605849

#	Time	Username	Problem	Language	Result	Execution time	Memory
605849		Zanite	ICC (CEOI16_icc)	C++17	100 / 100	139 ms	488 KiB

icc

#include "icc.h"

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

vector<vector<int>> component;

int _query(vector<int> &A, vector<int> &B) {
    int as = A.size(), bs = B.size();
    int a[as], b[bs];
    for (int i = 0; i < as; i++) {a[i] = A[i];}
    for (int i = 0; i < bs; i++) {b[i] = B[i];}
    return query(as, bs, a, b);
}

void run(int N) {
    for (int i = 1; i <= N; i++) {component.push_back({i});}

    for (int edge = 0; edge < N-1; edge++) {
        int CC = N - edge;
        int XOR = 0;

        // find a ^ b
        // log(CC) queries
        int K = 31 - __builtin_clz(CC);
        for (int b = 0; b <= K; b++) {
            vector<int> Zero, One;
            for (int i = 0; i < CC; i++) {
                if (i & (1 << b)) {
                    for (auto j : component[i]) {One.push_back(j);}
                } else {
                    for (auto j : component[i]) {Zero.push_back(j);}
                }
            }
            if (_query(Zero, One)) {XOR |= (1 << b);}
        }

        // endpoints and their CCs
        int E1, E2;
        int C1, C2;

        // find the first endpoint of the edge
        // log(CC/2) queries
        vector<int> Small, Large;
        for (int i = 0; i < CC; i++) {
            int j = i ^ XOR;
            if ((j < i) || (j >= CC)) continue;

            int a = i, b = j;
            if (component[a].size() > component[b].size()) {swap(a, b);}
            for (auto x : component[a]) {Small.push_back(x);}
            for (auto y : component[b]) {Large.push_back(y);}
        }
        // binary search
        int ss = Small.size();
        int L = 0, R = ss-1, bans = -1;
        while (L <= R) {
            int M = (L + R) >> 1;
            vector<int> binserQuery;
            for (int i = 0; i <= M; i++) {binserQuery.push_back(Small[i]);}

            if (_query(binserQuery, Large)) {
                bans = M;
                R = M - 1;
            } else {
                L = M + 1;
            }
        }
        E1 = Small[bans];
        for (int i = 0; i < CC; i++) {
            for (auto j : component[i]) if (E1 == j) C1 = i;
        }

        // find the second endpoint of the edge
        // log(N - CC + 1) queries
        C2 = C1 ^ XOR;
        int cs = component[C2].size();
        L = 0, R = cs-1; int cans = -1;
        vector<int> _E1 = {E1};
        while (L <= R) {
            int M = (L + R) >> 1;
            vector<int> binserQuery;
            for (int i = 0; i <= M; i++) {binserQuery.push_back(component[C2][i]);}

            if (_query(binserQuery, _E1)) {
                cans = M;
                R = M - 1;
            } else {
                L = M + 1;
            }
        }
        E2 = component[C2][cans];

        setRoad(E1, E2);
        for (auto i : component[C2]) {component[C1].push_back(i);}
        swap(component[C2], component[CC-1]);
        component.pop_back();
    }
}

Compilation message (stderr)

icc.cpp: In function 'void run(int)':
icc.cpp:76:12: warning: 'C1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |         C2 = C1 ^ XOR;
      |         ~~~^~~~~~~~~~

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