#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
const int MAXN = 1005;
vector<int> adj[MAXN];
int clr[MAXN], ans[MAXN], dest[MAXN], found;
bool query(int l, int r, int x, vector<int> &v){
vector<int> qvec;
for (int i = l; i <= r; i++) qvec.push_back(v[i]);
qvec.push_back(x);
return (Query(qvec) != qvec.size());
}
void bs(int x, vector<int> &v){
int pos = 0, vsz = v.size();
while (found < 3 && pos < vsz){
if (!query(pos, vsz - 1, x, v)) return;
int l = pos, r = vsz - 1;
while (l < r){
int m = (l + r) >> 1;
if (query(l, m, x, v)) r = m;
else l = m + 1;
}
adj[x].push_back(v[r]); adj[v[r]].push_back(x);
found++;
pos = r + 1;
}
}
void dfs(int x, int c){
clr[x] = c;
for (int nxt : adj[x])
if (clr[nxt] == -1)
dfs(nxt, 1 - c);
}
} // namespace
void Solve(int N) {
vector<int> grps[2];
for (int i = 1; i <= 2 * N; i++){
found = 0;
bs(i, grps[0]); bs(i, grps[1]);
memset(clr, -1, sizeof(clr));
for (int j = 1; j <= i; j++)
if (clr[j] == -1)
dfs(j, 0);
grps[0].clear(); grps[1].clear();
for (int j = 1; j <= i; j++) grps[clr[j]].push_back(j);
}
memset(dest, -1, sizeof(dest));
for (int i = 1; i <= 2 * N; i++){
if (adj[i].size() == 1) ans[i] = adj[i][0];
else{
for (int k = 0; k <= 2; k++){
vector<int> qvec; qvec.push_back(i);
for (int ind = 0; ind <= 2; ind++)
if (ind != k)
qvec.push_back(adj[i][ind]);
if (Query(qvec) == 1){
dest[i] = adj[i][k];
break;
}
}
}
}
for (int i = 1; i <= 2 * N; i++){
if (adj[i].size() == 1) continue;
for (int k = 0; k <= 2; k++)
if (adj[i][k] != dest[i] && dest[adj[i][k]] != i){
ans[i] = adj[i][k];
break;
}
}
for (int i = 1; i <= 2 * N; i++)
if (ans[i] > i)
Answer(i, ans[i]);
}
Compilation message
chameleon.cpp: In function 'bool {anonymous}::query(int, int, int, std::vector<int>&)':
chameleon.cpp:14:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | return (Query(qvec) != qvec.size());
| ~~~~~~~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
412 KB |
Output is correct |
| 3 |
Correct |
13 ms |
344 KB |
Output is correct |
| 4 |
Correct |
13 ms |
508 KB |
Output is correct |
| 5 |
Correct |
13 ms |
344 KB |
Output is correct |
| 6 |
Correct |
15 ms |
344 KB |
Output is correct |
| 7 |
Correct |
14 ms |
508 KB |
Output is correct |
| 8 |
Correct |
14 ms |
344 KB |
Output is correct |
| 9 |
Correct |
13 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Correct |
0 ms |
344 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Correct |
0 ms |
344 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Correct |
0 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
344 KB |
Output is correct |
| 11 |
Correct |
1 ms |
344 KB |
Output is correct |
| 12 |
Correct |
1 ms |
344 KB |
Output is correct |
| 13 |
Correct |
1 ms |
344 KB |
Output is correct |
| 14 |
Correct |
1 ms |
344 KB |
Output is correct |
| 15 |
Correct |
1 ms |
344 KB |
Output is correct |
| 16 |
Correct |
1 ms |
344 KB |
Output is correct |
| 17 |
Correct |
1 ms |
344 KB |
Output is correct |
| 18 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
25 ms |
512 KB |
Output is correct |
| 4 |
Correct |
31 ms |
600 KB |
Output is correct |
| 5 |
Correct |
25 ms |
344 KB |
Output is correct |
| 6 |
Correct |
25 ms |
508 KB |
Output is correct |
| 7 |
Correct |
25 ms |
516 KB |
Output is correct |
| 8 |
Correct |
25 ms |
344 KB |
Output is correct |
| 9 |
Correct |
25 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
412 KB |
Output is correct |
| 3 |
Correct |
13 ms |
344 KB |
Output is correct |
| 4 |
Correct |
13 ms |
508 KB |
Output is correct |
| 5 |
Correct |
13 ms |
344 KB |
Output is correct |
| 6 |
Correct |
15 ms |
344 KB |
Output is correct |
| 7 |
Correct |
14 ms |
508 KB |
Output is correct |
| 8 |
Correct |
14 ms |
344 KB |
Output is correct |
| 9 |
Correct |
13 ms |
344 KB |
Output is correct |
| 10 |
Correct |
0 ms |
344 KB |
Output is correct |
| 11 |
Correct |
0 ms |
344 KB |
Output is correct |
| 12 |
Correct |
0 ms |
344 KB |
Output is correct |
| 13 |
Correct |
0 ms |
344 KB |
Output is correct |
| 14 |
Correct |
0 ms |
344 KB |
Output is correct |
| 15 |
Correct |
0 ms |
344 KB |
Output is correct |
| 16 |
Correct |
0 ms |
344 KB |
Output is correct |
| 17 |
Correct |
0 ms |
344 KB |
Output is correct |
| 18 |
Correct |
0 ms |
344 KB |
Output is correct |
| 19 |
Correct |
1 ms |
344 KB |
Output is correct |
| 20 |
Correct |
1 ms |
344 KB |
Output is correct |
| 21 |
Correct |
1 ms |
344 KB |
Output is correct |
| 22 |
Correct |
1 ms |
344 KB |
Output is correct |
| 23 |
Correct |
1 ms |
344 KB |
Output is correct |
| 24 |
Correct |
1 ms |
344 KB |
Output is correct |
| 25 |
Correct |
1 ms |
344 KB |
Output is correct |
| 26 |
Correct |
1 ms |
344 KB |
Output is correct |
| 27 |
Correct |
1 ms |
344 KB |
Output is correct |
| 28 |
Correct |
0 ms |
344 KB |
Output is correct |
| 29 |
Correct |
0 ms |
344 KB |
Output is correct |
| 30 |
Correct |
25 ms |
512 KB |
Output is correct |
| 31 |
Correct |
31 ms |
600 KB |
Output is correct |
| 32 |
Correct |
25 ms |
344 KB |
Output is correct |
| 33 |
Correct |
25 ms |
508 KB |
Output is correct |
| 34 |
Correct |
25 ms |
516 KB |
Output is correct |
| 35 |
Correct |
25 ms |
344 KB |
Output is correct |
| 36 |
Correct |
25 ms |
344 KB |
Output is correct |
| 37 |
Correct |
27 ms |
344 KB |
Output is correct |
| 38 |
Correct |
13 ms |
344 KB |
Output is correct |
| 39 |
Correct |
26 ms |
344 KB |
Output is correct |
| 40 |
Correct |
27 ms |
344 KB |
Output is correct |
| 41 |
Correct |
27 ms |
344 KB |
Output is correct |
| 42 |
Correct |
13 ms |
344 KB |
Output is correct |
| 43 |
Correct |
25 ms |
344 KB |
Output is correct |
| 44 |
Correct |
27 ms |
344 KB |
Output is correct |
| 45 |
Correct |
28 ms |
344 KB |
Output is correct |
