| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 221643 |
2020-04-10T17:28:51 Z |
rama_pang |
ICC (CEOI16_icc) |
C++14 |
|
151 ms |
636 KB |
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
vector<vector<int>> components;
int Query(vector<int> A, vector<int> B) {
if (A.empty() || B.empty()) return 0;
return query(A.size(), B.size(), A.data(), B.data());
}
int QueryComponent(vector<int> A, vector<int> B) {
vector<int> P, Q;
for (auto i : A) {
for (auto j : components[i]) {
P.emplace_back(j);
}
}
for (auto i : B) {
for (auto j : components[i]) {
Q.emplace_back(j);
}
}
return Query(P, Q);
}
void Answer(int A, int B) {
return setRoad(A, B);
}
pair<int, int> BinarySearch(vector<int> A, vector<int> B, bool onComponent) {
if (A.size() < B.size()) swap(A, B);
if (A.size() == 1 && B.size() == 1) return {A[0], B[0]};
int mid = A.size() / 2;
vector<int> L(begin(A), begin(A) + mid), R(begin(A) + mid, end(A));
bool res;
if (onComponent) {
if (R.empty() || QueryComponent(L, B)) {
return BinarySearch(L, B, onComponent);
} else {
return BinarySearch(R, B, onComponent);
}
} else {
if (R.empty() || Query(L, B)) {
return BinarySearch(L, B, onComponent);
} else {
return BinarySearch(R, B, onComponent);
}
}
}
void MergeComponent(int C1, int C2) {
vector<int> Merged;
for (auto i : components[C1]) Merged.emplace_back(i);
for (auto i : components[C2]) Merged.emplace_back(i);
components[C1].clear();
components[C2].clear();
sort(begin(components), end(components), [&](const vector<int> &a, const vector<int> &b) {
return a.size() > b.size();
});
while (!components.empty() && components.back().empty()) components.pop_back();
components.emplace_back(Merged);
}
pair<int, int> RecoverFromXor(int Xor) {
int X = 0;
int resA = 0, resB = 0;
for (int i = 0; i < 7; i++) {
if (Xor & (1 << i)) {
X = i;
resB |= 1 << i;
break;
}
}
for (int i = 0; i < 7; i++) {
if (i == X) continue;
if (Xor & (1 << i)) { // i-th bit in Xor is ON, so we query check if A = 0 and B = 1 or otherwise
vector<int> A, B;
for (int k = 0; k < components.size(); k++) {
if ((k & (1 << i)) && (k & (1 << X))) { // i-th and X-th bit is ON
B.emplace_back(k);
} else if (!(k & (1 << i)) && !(k & (1 << X))) {
A.emplace_back(k);
}
}
if (QueryComponent(A, B)) { // A = 0 and B = 1
resB |= 1 << i;
} else {
resA |= 1 << i;
}
} else { // Check if A = B = 0 or A = B = 1
vector<int> A, B;
for (int k = 0; k < components.size(); k++) {
if ((k & (1 << i)) && (k & (1 << X))) { // i-th and X-th bit is ON
B.emplace_back(k);
} else if ((k & (1 << i)) && !(k & (1 << X))) {
A.emplace_back(k);
}
}
if (QueryComponent(A, B)) { // A = 1 and B = 1
resA |= 1 << i;
resB |= 1 << i;
}
}
}
return {resA, resB};
}
void run(int N) {
for (int i = 1; i <= N; i++) {
components.emplace_back(vector<int>{i});
}
for (int i = 1; i < N; i++) {
int Xor = 0;
for (int j = 0; j < 7; j++) {
vector<int> A, B;
for (int k = 0; k < components.size(); k++) {
if (k & (1 << j)) {
A.emplace_back(k);
} else {
B.emplace_back(k);
}
}
if (QueryComponent(A, B)) {
Xor |= 1 << j;
}
}
// Binary Search to find edge's endpoint
auto TwoComp = RecoverFromXor(Xor);
auto Edge = BinarySearch(components[TwoComp.first], components[TwoComp.second], false);
Answer(Edge.first, Edge.second);
MergeComponent(TwoComp.first, TwoComp.second);
}
}
Compilation message
icc.cpp: In function 'std::pair<int, int> BinarySearch(std::vector<int>, std::vector<int>, bool)':
icc.cpp:39:8: warning: unused variable 'res' [-Wunused-variable]
bool res;
^~~
icc.cpp: In function 'std::pair<int, int> RecoverFromXor(int)':
icc.cpp:84:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int k = 0; k < components.size(); k++) {
~~^~~~~~~~~~~~~~~~~~~
icc.cpp:98:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int k = 0; k < components.size(); k++) {
~~^~~~~~~~~~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:124:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int k = 0; k < components.size(); k++) {
~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
512 KB |
Ok! 114 queries used. |
| 2 |
Correct |
11 ms |
512 KB |
Ok! 113 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
512 KB |
Ok! 641 queries used. |
| 2 |
Correct |
42 ms |
512 KB |
Ok! 547 queries used. |
| 3 |
Correct |
44 ms |
512 KB |
Ok! 565 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
151 ms |
568 KB |
Ok! 1552 queries used. |
| 2 |
Correct |
133 ms |
512 KB |
Ok! 1351 queries used. |
| 3 |
Correct |
151 ms |
512 KB |
Ok! 1531 queries used. |
| 4 |
Correct |
147 ms |
512 KB |
Ok! 1520 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
140 ms |
512 KB |
Ok! 1500 queries used. |
| 2 |
Correct |
144 ms |
512 KB |
Ok! 1499 queries used. |
| 3 |
Correct |
146 ms |
512 KB |
Ok! 1463 queries used. |
| 4 |
Correct |
150 ms |
512 KB |
Ok! 1550 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
144 ms |
512 KB |
Ok! 1463 queries used. |
| 2 |
Correct |
141 ms |
512 KB |
Ok! 1467 queries used. |
| 3 |
Correct |
138 ms |
636 KB |
Ok! 1465 queries used. |
| 4 |
Correct |
141 ms |
512 KB |
Ok! 1484 queries used. |
| 5 |
Correct |
148 ms |
512 KB |
Ok! 1548 queries used. |
| 6 |
Correct |
140 ms |
512 KB |
Ok! 1489 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
143 ms |
512 KB |
Ok! 1470 queries used. |
| 2 |
Correct |
149 ms |
512 KB |
Ok! 1463 queries used. |
