#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
int variable_example = 1;
} // namespace
vector<int> way[1004];
int chk[1004];
vector<int> l, r;
void Solve(int n) {
for(int i = 1; i <= n * 2; ++i){
int lr = 0;
auto ask = l;
ask.push_back(i);
if(Query(ask) != (int)ask.size()){
lr = 1;
}
// cout << lr << endl;
auto add = [&](vector<int> x, int now){
// auto ask = x;
// ask.push_back(now);
// if(Query(ask) == (int)ask.size()){
// return;
// }
int pos = 0;
while(pos < (int)x.size()){
int low = pos, high = (int)x.size();
while(low < high){
int mid = low + high >> 1;
vector<int> inask;
for(int j = low; j <= mid; ++j){
inask.push_back(x[j]);
}
inask.push_back(now);
if(Query(inask) == (int)inask.size()){
low = mid + 1;
}
else{
high = mid;
}
}
if(low == (int)x.size()) return;
way[now].push_back(x[low]);
way[x[low]].push_back(now);
pos = low + 1;
}
};
add(lr ? l : r, i);
int sz = (int)way[i].size();
if(lr) add(r, i);
auto flip = [&](auto&&self, int x, int pr, int col)->void{
if(col == 1){
int p = 0;
while(x != r[p]) ++p;
swap(r[p], r.back());
r.pop_back();
l.push_back(x);
}
else{
int p = 0;
while(x != l[p]) ++p;
swap(l[p], l.back());
l.pop_back();
r.push_back(x);
}
for(auto&nxt:way[x]){
if(nxt == pr || nxt > i) continue;
self(self, nxt, x, 1 - col);
}
};
for(int j = sz; j < (int)way[i].size(); ++j){
assert(0);
flip(flip, way[i][j], i, 1);
}
if(!lr) l.push_back(i);
else r.push_back(i);
}
// if((int)l.size() != n || (int)r.size() != n) while(true){}
auto del = [&](int x, int y)->void{
for(int i = 0; i < (int)way[x].size(); ++i){
if(way[x][i] == y){
swap(way[x][i], way[x].back());
way[x].pop_back();
return;
}
}
assert(0);
};
while(true){
int ed = 1;
for(int i = 1; i <= n * 2; ++i){
if((int)way[i].size() < 3){
continue;
}
ed = 0;
assert((int)way[i].size() == 3);
for(int j = 0; j < 3; ++j){
vector<int> ask = {i};
for(int x = 0; x < 3; ++x){
if(j != x){
ask.push_back(way[i][x]);
}
}
int rv = Query(ask);
if(rv == 1){
// del(way[i][j], i);
del(i, way[i][j]);
break;
}
}
assert((int)way[i].size() == 2);
}
if(ed) break;
}
for(int i = 1; i <= n * 2; ++i){
for(int j = 0; j < (int)way[i].size(); ++j){
int nxt = way[i][j];
int fd = 0;
for(auto&nnxt:way[nxt]){
fd |= nnxt == i;
}
if(!fd){
swap(way[i][j], way[i].back());
way[i].pop_back();
}
}
}
vector<vector<int>> ans;
while((int)ans.size() < n){
for(int i = 1; i <= n * 2; ++i){
if(chk[i] || (int)way[i].size() > 1) continue;
assert((int)way[i].size() == 1);
int nxt = way[i][0];
chk[i] = chk[nxt] = 1;
ans.push_back({i, nxt});
for(auto&j:way[nxt]){
del(j, nxt);
}
way[nxt].clear();
way[i].clear();
}
}
for(auto&i:ans){
Answer(i[0], i[1]);
}
}
Compilation message
chameleon.cpp: In lambda function:
chameleon.cpp:38:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | int mid = low + high >> 1;
| ~~~~^~~~~~
chameleon.cpp: At global scope:
chameleon.cpp:7:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
7 | int variable_example = 1;
| ^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
17 ms |
336 KB |
Output is correct |
| 4 |
Correct |
17 ms |
412 KB |
Output is correct |
| 5 |
Correct |
17 ms |
408 KB |
Output is correct |
| 6 |
Correct |
17 ms |
428 KB |
Output is correct |
| 7 |
Correct |
17 ms |
420 KB |
Output is correct |
| 8 |
Correct |
17 ms |
412 KB |
Output is correct |
| 9 |
Correct |
17 ms |
336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
0 ms |
336 KB |
Output is correct |
| 4 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
0 ms |
336 KB |
Output is correct |
| 4 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
336 KB |
Output is correct |
| 2 |
Correct |
0 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
22 ms |
396 KB |
Wrong Answer [3] |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
17 ms |
336 KB |
Output is correct |
| 4 |
Correct |
17 ms |
412 KB |
Output is correct |
| 5 |
Correct |
17 ms |
408 KB |
Output is correct |
| 6 |
Correct |
17 ms |
428 KB |
Output is correct |
| 7 |
Correct |
17 ms |
420 KB |
Output is correct |
| 8 |
Correct |
17 ms |
412 KB |
Output is correct |
| 9 |
Correct |
17 ms |
336 KB |
Output is correct |
| 10 |
Correct |
0 ms |
336 KB |
Output is correct |
| 11 |
Correct |
1 ms |
336 KB |
Output is correct |
| 12 |
Correct |
0 ms |
336 KB |
Output is correct |
| 13 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 6 |
| 14 |
Halted |
0 ms |
0 KB |
- |
