oj.uz

Submission #984531

# Submission time Handle Problem Language Result Execution time Memory
984531 2024-05-16T18:18:43 Z Maaxle ICC (CEOI16_icc) C++17
100 / 100
 99 ms 852 KB 
#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 = floor(log2(comp.size()-1))+1;
    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;
        }
        int q = query(a, b, A, B);
        k |= (q << 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() - 1, 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

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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 604 KB Ok! 109 queries used.
2 Correct 4 ms 604 KB Ok! 107 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 604 KB Ok! 616 queries used.
2 Correct 19 ms 604 KB Ok! 455 queries used.
3 Correct 21 ms 604 KB Ok! 510 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 620 KB Ok! 1538 queries used.
2 Correct 57 ms 604 KB Ok! 1077 queries used.
3 Correct 74 ms 616 KB Ok! 1524 queries used.
4 Correct 76 ms 620 KB Ok! 1514 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 616 KB Ok! 1454 queries used.
2 Correct 74 ms 604 KB Ok! 1482 queries used.
3 Correct 76 ms 620 KB Ok! 1482 queries used.
4 Correct 76 ms 600 KB Ok! 1530 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 604 KB Ok! 1483 queries used.
2 Correct 71 ms 600 KB Ok! 1451 queries used.
3 Correct 67 ms 604 KB Ok! 1346 queries used.
4 Correct 73 ms 604 KB Ok! 1492 queries used.
5 Correct 75 ms 604 KB Ok! 1519 queries used.
6 Correct 74 ms 604 KB Ok! 1528 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 852 KB Ok! 1444 queries used.
2 Correct 64 ms 604 KB Ok! 1257 queries used.