Submission #212384

#TimeUsernameProblemLanguageResultExecution timeMemory
212384AbdullahChameleon's Love (JOI20_chameleon)C++17
44 / 100
37 ms504 KiB
#include "chameleon.h" #include <bits/stdc++.h> using namespace std; vector<vector<int>>S(4), B(1005), adjs(1005); vector<bool>vis(1005, 0); int y; void ans(int a, int b){ if(vis[a]||vis[b])return; Answer(a, b); vis[a]=1, vis[b]=1; return; } void BS(int x, int j, int l, int r){ if(adjs[x].size()==3)return; if(l==r){ adjs[x].push_back(S[j][l]); adjs[S[j][l]].push_back(x); return; } int m=(l+r)/2; vector<int>v1={x}, v2={x}; for(int i=l; i<=m; i++)v1.push_back(S[j][i]); for(int i=m+1; i<=r; i++)v2.push_back(S[j][i]); if(Query(v1)!=m-l+2){ BS(x, j, l, m); } if(adjs[x].size()==3)return; if(Query(v2)!=r-m+1){ BS(x, j, m+1, r); } } void Solve(int n) { n*=2; y=n; for(int i=1; i<=n; i++){ int x; for(int j=0; j<4; j++){ S[j].push_back(i); if(Query(S[j])!=S[j].size()){ S[j].pop_back(); BS(i, j, 0, S[j].size()-1); }else{ S[j].pop_back(); x=j; } } S[x].push_back(i); } for(int i=1; i<=n; i++){ if(adjs[i].size()==1){ ans(i, adjs[i][0]); }else{ for(int j=0; j<3; j++){ if(j==2){ B[i].push_back(adjs[i][j]); B[adjs[i][j]].push_back(i); break; } vector<int>A={i}; for(int a=0;a<=2; a++){ if(a!=j)A.push_back(adjs[i][a]); } if(Query(A)==1){ B[i].push_back(adjs[i][j]); B[adjs[i][j]].push_back(i); break; } } } } for(int i=1; i<=n; i++){ if(vis[i])continue; for(int a:adjs[i]){ if(a!=B[i][0]&&a!=B[i][1]){ ans(i, a); } } } } //~ #include "chameleon.h" //~ #include <bits/stdc++.h> //~ using namespace std; //~ int n; //~ int get(int x, int l ,int r, int y){ //~ vector<int>p; //~ if(y!=-1){ //~ for(int i=l; i<=r; i++)p.push_back(i); //~ p.push_back(y); //~ return Query(p); //~ }else if(x==-1){ //~ for(int i=l; i<=r; i++) p.push_back(i); //~ return Query(p); //~ }else{ //~ for(int i=l ; i<=r; i++){ //~ if(i==x)continue; //~ p.push_back(i); //~ } //~ return Query(p); //~ } //~ } //~ int rec(int x, int l, int r){ //~ int m=(l+r)/2; //~ if(l==r) return l; //~ if(x<=m){ //~ if(get(x, 1, m, -1)==get(-1, 1, m, -1)) return rec(x, 1, m); //~ else return rec(x, m+1, r); //~ }else{ //~ if(get(-1, 1, m, -1)==get(-1, 1, m, x)) return rec(x, 1, m); //~ else return rec(x, m+1, r); //~ } //~ } //~ void Solve(int N) { //~ n=N*2; //~ vector<bool>vis(n+1); //~ for(int i=1; i<=n; i++){ //~ if(vis[i])continue; //~ int j=rec(i, 1, n); //~ Answer(i, j); //~ vis[i]=1, vis[j]=1; //~ } //~ }

Compilation message (stderr)

chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:39:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(Query(S[j])!=S[j].size()){
       ~~~~~~~~~~~^~~~~~~~~~~~~
chameleon.cpp:47:6: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   S[x].push_back(i);
      ^
#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...