oj.uz

Submission #605849

# Submission time Handle Problem Language Result Execution time Memory
605849 2022-07-26T03:41:16 Z Zanite ICC (CEOI16_icc) C++17
100 / 100
 139 ms 488 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Ok! 123 queries used.
2 Correct 6 ms 488 KB Ok! 119 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 468 KB Ok! 635 queries used.
2 Correct 31 ms 480 KB Ok! 532 queries used.
3 Correct 34 ms 480 KB Ok! 580 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 488 KB Ok! 1554 queries used.
2 Correct 104 ms 480 KB Ok! 1255 queries used.
3 Correct 108 ms 484 KB Ok! 1551 queries used.
4 Correct 112 ms 468 KB Ok! 1525 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 480 KB Ok! 1508 queries used.
2 Correct 113 ms 484 KB Ok! 1495 queries used.
3 Correct 114 ms 484 KB Ok! 1588 queries used.
4 Correct 114 ms 484 KB Ok! 1547 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 484 KB Ok! 1520 queries used.
2 Correct 115 ms 484 KB Ok! 1588 queries used.
3 Correct 109 ms 468 KB Ok! 1443 queries used.
4 Correct 139 ms 480 KB Ok! 1599 queries used.
5 Correct 122 ms 480 KB Ok! 1559 queries used.
6 Correct 112 ms 484 KB Ok! 1606 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 468 KB Ok! 1511 queries used.
2 Correct 106 ms 480 KB Ok! 1356 queries used.