oj.uz

Submission #984437

# Submission time Handle Problem Language Result Execution time Memory
984437 2024-05-16T16:32:15 Z Maaxle ICC (CEOI16_icc) C++17
0 / 100
 1 ms 860 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 = 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

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

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -