## 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;
}

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++) {
}
}```

### 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 -