Submission #444258

#TimeUsernameProblemLanguageResultExecution timeMemory
444258kig9981Chameleon's Love (JOI20_chameleon)C++17
100 / 100
81 ms504 KiB
#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 check(int v, int l, int r, int i) { if(l>r || adj[i].size()==3) return; int s=l, e=r; while(s<=e) { int m=(s+e)>>1; Q.clear(); Q.push_back(i); for(int k=l;k<=m;k++) Q.push_back(V[v][k]); if(Query(Q)==Q.size()) s=m+1; else e=m-1; } if(s>r) return; adj[V[v][s]].push_back(i); adj[i].push_back(V[v][s]); check(v,s+1,r,i); } 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); V[0].push_back(i); if(Query(V[0])^V[0].size()) check(0,0,V[0].size()-2,i); V[1].push_back(i); if(Query(V[1])^V[1].size()) check(1,0,V[1].size()-2,i); } memset(chk,0,sizeof(chk)); for(int i=1;i<=2*N;i++) { if(adj[i].size()==1) { if(!chk[i]) 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(adj[i][k]); if(Query(Q)==1) { E[i].push_back(adj[i][j]); E[adj[i][j]].push_back(i); break; } } } for(int i=1;i<=2*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 (stderr)

chameleon.cpp: In function 'void check(int, int, int, int)':
chameleon.cpp:33:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   if(Query(Q)==Q.size()) s=m+1;
      |      ~~~~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...