Submission #984437

#	Time	Username	Problem	Language	Result	Execution time	Memory
984437		Maaxle	ICC (CEOI16_icc)	C++17	0 / 100	1 ms	860 KiB

icc

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

#define range(it, a, b) for (ll it = a; it < b; it++)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define INF64 ((ll) 1 << 62)
#define INF32 (1 << 30)
#define mset multiset
#define uset unordered_set
#define umap unordered_map 
#define pqueue priority_queue 
#define ptr(A) shared_ptr<A>

#define iter(x) set<x>::iterator

using namespace std;

int n;
vector<vector<int>> comp;

bool queryRange(vector<pair<int, int>>& c, int& l, int& r) {
    int a = 0, b = 0;
    int A[n], B[n];

    for (int i = l; i <= r; i++) {
        for (int& x : comp[c[i].first])
            A[a++] = x;
        for (int& x : comp[c[i].second])
            B[b++] = x;
    }
    return query(a, b, A, B);
}

bool queryRange(int& l, int& r, int A[], int& b, int B[]) {
    int c = 0;
    int C[n];

    for (int i = l; i <= r; i++)
        C[c++] = A[i];
    
    return query(c, b, C, B);
}

pair<int, int> BSComp(int& a, int& b, int A[], int B[]) {
    pair<int, int> ans;

    // BINARY-SEARCH FIRST COMPONENT
    int l = 0, r = a-1, m;
    while (l < r) {
        m = (l+r)/2;

        if (queryRange(l, m, A, b, B))
            r = m;
        else l = m+1;     
    }
    ans.first = A[l];

    // BINATY-SEARCH SECOND COMPONENT
    l = 0; r = b-1;
    while (l < r) {
        m = (l+r)/2;

        if (queryRange(l, m, B, a, A))
            r = m;
        else l = m+1;
    }
    ans.second = B[l];

    return ans;
}

void findEdge() {
    // QUERY COMPONENTS BITWISE
    int k = 0;
    int LOG = ceil(log2(comp.size()));
    for (int bt = 0; bt < LOG; bt++) {
        int a = 0, b = 0;
        int A[n], B[n];

        for (int it = 0; it < comp.size(); it++) {
            if (it & (1 << bt)) {
                for (int& x : comp[it])
                    A[a++] = x;
                continue;
            }
            for (int& x : comp[it])
                B[b++] = x;
        }

        k &= (query(a, b, A, B) << bt);
    }

    // FORM CANDIDATES PAIRS WITH THE FOUND XOR
    vector<pair<int, int>> candidates;
    for (int x = 0; x < comp.size(); x++) {
        int y = x^k;
        if (x < y && y < comp.size())
            candidates.push_back({x, y});
    }

    // BINARY-SEARCH BETWEEN CADIDATES
    int l = 0, r = candidates.size(), m;
    while (l < r) {
        m = (l+r)/2;
        if (queryRange(candidates, l, m))
            r = m;
        else l = m+1;
    }

    int a = 0, b = 0;
    int A[n], B[n];
    for (int& x : comp[candidates[l].first])
        A[a++] = x;
    for (int& x : comp[candidates[l].second])
        B[b++] = x;

    // BINARY-SEARCH COMPONENTS
    auto ans = BSComp(a, b, A, B);
    setRoad(ans.first, ans.second);

    // MERGE COMPONENTS
    comp[candidates[l].first].insert(end(comp[candidates[l].first]), all(comp[candidates[l].second]));
    comp.erase(begin(comp)+candidates[l].second);
}

void run(int N) {
    n = N;

    for (int i = 0; i < N; i++)
        comp.push_back({i+1});
    
    for (int i = 0; i < N-1; i++)
        findEdge();
}

Compilation message (stderr)

icc.cpp: In function 'void findEdge()':
icc.cpp:82:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for (int it = 0; it < comp.size(); it++) {
      |                          ~~~^~~~~~~~~~~~~
icc.cpp:97:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for (int x = 0; x < comp.size(); x++) {
      |                     ~~^~~~~~~~~~~~~
icc.cpp:99:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         if (x < y && y < comp.size())
      |                      ~~^~~~~~~~~~~~~

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