oj.uz

Submission #983659

# Submission time Handle Problem Language Result Execution time Memory
983659 2024-05-15T21:42:25 Z Maaxle ICC (CEOI16_icc) C++17
0 / 100
 10 ms 3928 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;
set<vector<int>> nodes;

iter(vector<int>) searchGroup(int s, iter(vector<int>) begin, int& b, int B[]) {
    // END RECURSION FOR ONE SINGLE NODE
    if (s == 1) {
        int A[(*begin).size()];
        int i = 0;
        for (int it : (*begin)) 
            A[i++] = it;

        if (query((*begin).size(), b, A, B))
            return begin;
        return end(nodes);
    }

    // PARTITION THE ARRAYS INTO TWO GROUPS
    int A[n], C[n];
    int a = 0, c = 0;
    int m = (s-1)/2;
    int s1 = m+1;
    int s2 = s - s1;
    iter(vector<int>) cur = begin, mid;

    for (int i = 0; i < s; i++) {
        if (i <= m) {
            for (int it : (*cur))
                A[a++] = it;
            continue;
        }

        if (i == m+1)
            mid = cur;
        
        for (int it : (*cur))
            C[c++] = it;
    }

    // LOOK IN CONNECTED HALF
    if (query(a, b, A, B))
        return searchGroup(s1, begin, b, B);
    return searchGroup(s2, mid, b, B);
}

pair<iter(vector<int>), iter(vector<int>)> checkForGroups (int s, iter(vector<int>) begin) {
    // IF ONLY ONE GROUP => RETURN UNSUCCESSFUL
    if (s == 1)
        return {end(nodes), end(nodes)};
    
    iter(vector<int>) cur = begin, mid;
    int a = 0, b = 0;
    int A[n], B[n];
    int m = (s-1)/2;
    int s1 = m+1;
    int s2 = s-s1;
    
    // PARTITION THE ARRAYS IN TWO GROUPS
    for (int i = 0; i < s; i++, cur++) {
        if (i <= m) {
            for (int it : *cur)
                A[a++] = it;
            continue;
        }
        if (i == m+1)
            mid = cur;

        for (int it : *cur)
            B[b++] = it;
    }
    bool resp = query(a, b, A, B);
    
    // IF THE PARTITION IS CONNECTED => LOOK FOR SPECIFIC GROUPS
    if (resp) {
        pair<iter(vector<int>), iter(vector<int>)> ans;
        ans.first = searchGroup(s1, begin, b, B);
        ans.second = searchGroup(s2, mid, a, A);
        return ans;
    }

    // IF NOT CONNECTED => SEARCH RECURSIVELY IN BOTH HALVES
    pair<iter(vector<int>), iter(vector<int>)> ans = checkForGroups(s1, begin);
    if (ans.first != end(nodes))
        return ans;
    ans = checkForGroups(s2, mid);
    return ans;
}

int searchNode(int l, int r, iter(vector<int>) g, int& b, int B[]) {
    if (l == r) {
        int q[1] = {(*g)[l]};
        return (query(1, b, q, B) ? (*g)[l] : -1);
    }

    int m = (l+r)/2;
    int a = 0, c = 0;
    int A[n], C[n];

    // PARTITION INTO TWO HALVES
    for (int i = l; i <= r; i++) {
        if (i <= m) {
            A[a++] = (*g)[i];
            continue;
        }
        C[c++] = (*g)[i];
    }

    // SEARCH IN CONNECTED HALF
    if (query(a, b, A, B)) 
        return searchNode(l, m, g, b, B);
    return searchNode(m+1, r, g, b, B);
}

pair<int, int> betweenGroups (iter(vector<int>) x, iter(vector<int>) y) {
    int a = (*x).size();
    int b = (*y).size();
    int A[a], B[b];
    pair<int, int> ans = {searchNode(0, a-1, x, b, B), searchNode(0, b-1, y, a, A)};
    return ans;
}

pair<int, int> getRoad() {
    int l = 0, r = nodes.size()-1;
    pair<iter(vector<int>), iter(vector<int>)> a = checkForGroups(r-l+1, nodes.begin());
    pair<int, int> ans = betweenGroups(a.first, a.second);

    vector<int> x = *(a.first), y = *(a.second);
    if (x.size() > y.size())
        swap(x, y);
    for (int& it : x)
        y.push_back(it);

    nodes.erase(*(a.first));
    nodes.erase(*(a.second));
    nodes.insert(y);

    return ans;
}

void run(int N) {
    n = N;
    for (int i = 0; i < N; i++)
        nodes.insert({i+1});
    
    for (int i = 0; i < N-1; i++) {
        pair<int, int> ans = getRoad();
        setRoad(ans.first, ans.second);
    }
}

Compilation message

icc.cpp: In function 'std::set<std::vector<int> >::iterator searchGroup(int, std::set<std::vector<int> >::iterator, int&, int*)':
icc.cpp:37:15: warning: variable 'C' set but not used [-Wunused-but-set-variable]
   37 |     int A[n], C[n];
      |               ^
icc.cpp: In function 'int searchNode(int, int, std::set<std::vector<int> >::iterator, int&, int*)':
icc.cpp:115:15: warning: variable 'C' set but not used [-Wunused-but-set-variable]
  115 |     int A[n], C[n];
      |               ^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 856 KB Number of queries more than 3000 out of 1500
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2396 KB Number of queries more than 5000 out of 2500
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 3928 KB Number of queries more than 4500 out of 2250
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 604 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 604 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 2908 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -