#include "chameleon.h"
#include <bits/stdc++.h>
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
using namespace std;
vector<int> adj[1001], V[2], Q, E[1001];
int P[1001];
bool chk[1001];
void dfs(int c, int v)
{
V[v].push_back(c);
chk[c]=true;
for(auto n: adj[c]) if(!chk[n]) dfs(n,v^1);
}
void Solve(int N)
{
for(int i=1;i<=2*N;i++) {
V[0].clear(); V[1].clear();
for(int j=1;j<i;j++) chk[j]=false;
for(int j=1;j<i;j++) if(!chk[j]) dfs(j,0);
for(int l=-1;l<V[0].size();) {
int s=l+1, e=V[0].size()-1;
while(s<=e) {
int m=(s+e)>>1;
Q.clear(); Q.push_back(i);
for(int k=l+1;k<=m;k++) Q.push_back(V[0][k]);
if(Query(Q)==Q.size()) s=m+1;
else e=m-1;
}
if(s==V[0].size()) break;
adj[V[0][s]].push_back(i);
adj[i].push_back(V[0][s]);
l=s;
}
for(int l=-1;l<V[1].size();) {
int s=l+1, e=V[1].size()-1;
while(s<=e) {
int m=(s+e)>>1;
Q.clear(); Q.push_back(i);
for(int k=l+1;k<=m;k++) Q.push_back(V[1][k]);
if(Query(Q)==Q.size()) s=m+1;
else e=m-1;
}
if(s==V[1].size()) break;
adj[V[1][s]].push_back(i);
adj[i].push_back(V[1][s]);
l=s;
}
}
memset(chk,0,sizeof(chk));
for(int i=1;i<=N;i++) if(!chk[i]) {
if(adj[i].size()==1) {
Answer(i,adj[i][0]);
chk[i]=chk[adj[i][0]]=true;
continue;
}
for(int j=0;j<3;j++) {
Q.clear(); Q.push_back(i);
for(int k=0;k<3;k++) if(k^j) Q.push_back(k);
if(Query(Q)==1) {
P[i]=adj[i][j];
break;
}
}
E[i].push_back(P[i]);
E[P[i]].push_back(i);
}
for(int i=1;i<=N;i++) if(!chk[i]) {
for(auto a: adj[i]) {
bool valid=true;
for(auto b: E[i]) if(a==b) valid=false;
if(valid) {
Answer(i,a);
chk[i]=chk[a]=true;
break;
}
}
}
}
Compilation message
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:31:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int l=-1;l<V[0].size();) {
| ~^~~~~~~~~~~~
chameleon.cpp:37:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | if(Query(Q)==Q.size()) s=m+1;
| ~~~~~~~~^~~~~~~~~~
chameleon.cpp:40:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | if(s==V[0].size()) break;
| ~^~~~~~~~~~~~~
chameleon.cpp:45:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int l=-1;l<V[1].size();) {
| ~^~~~~~~~~~~~
chameleon.cpp:51:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | if(Query(Q)==Q.size()) s=m+1;
| ~~~~~~~~^~~~~~~~~~
chameleon.cpp:54:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | if(s==V[1].size()) break;
| ~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
328 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
328 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
328 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
328 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
328 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
