Submission #946948

#TimeUsernameProblemLanguageResultExecution timeMemory
946948onepunchac168Chameleon's Love (JOI20_chameleon)C++14
100 / 100
41 ms788 KiB
#include "chameleon.h" #include <bits/stdc++.h> using namespace std; int n; const int N=1005; vector <int> vt[N]; bool fee[N]; vector <int> cnt[2]; bool f[N]; void dfs(int u,bool ok) { cnt[ok].push_back(u); f[u]=1; for (auto v:vt[u]) { if (f[v]==1) { continue; } dfs(v,1-ok); } } int stl[N]; int ans[N]; void solvea(vector <int >targeta,int id) { int left=0; int right=targeta.size()-1; while (left<=right) { vector <int> tmp; for (int i=left; i<=right; i++) { tmp.push_back(targeta[i]); } tmp.push_back(id); if (Query(tmp)==int(tmp.size())) { break; } int lefta=left; int righta=right; int lmao; while (lefta<=righta) { int mid=(lefta+righta)/2; vector <int> res; for (int i=lefta; i<=mid; i++) { res.push_back(targeta[i]); } res.push_back(id); if (Query(res)<int(res.size())) { lmao=mid; righta=mid-1; } else lefta=mid+1; } vt[id].push_back(targeta[lmao]); vt[targeta[lmao]].push_back(id); left=lmao+1; } } void Solve(int N) { n=N; for (int i=1; i<=n*2; i++) { fee[i]=0; } vector <int> targeta,targetb; while (true) { int id=-1; for (int i=1; i<=n*2; i++) { if (fee[i]==0) { id=i; break; } } if (id==-1) { break; } fee[id]=1; solvea(targeta,id); solvea(targetb,id); for (int i=1; i<=n*2; i++) { f[i]=0; } cnt[0].clear(); cnt[1].clear(); for (int i=1; i<=n*2; i++) { if (f[i]==0&&fee[i]==1) { dfs(i,0); } } swap(targeta,cnt[0]); swap(targetb,cnt[1]); } #define pb push_back for (int i=1;i<=2*n;i++) { if (vt[i].size()==3) { vector <int> opt1,opt2; opt1.pb(i);opt1.pb(vt[i][0]);opt1.pb(vt[i][1]); opt2.pb(i);opt2.pb(vt[i][0]);opt2.pb(vt[i][2]); if (Query(opt1)==1) { stl[i]=vt[i][2]; } else if (Query(opt2)==1) { stl[i]=vt[i][1]; } else stl[i]=vt[i][0]; } else { ans[i]=vt[i][0]; } } for (int i=1;i<=2*n;i++) { if (vt[i].size()==3) { int id; for (auto v:vt[i]) { if (stl[v]==i||stl[i]==v) { continue; } id=v; } ans[i]=id; } } for (int i=1;i<=2*n;i++) { if (i<ans[i]) { Answer(i,ans[i]); } } }

Compilation message (stderr)

chameleon.cpp: In function 'void solvea(std::vector<int>, int)':
chameleon.cpp:65:13: warning: 'lmao' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |         left=lmao+1;
      |         ~~~~^~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:146:19: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
  146 |             ans[i]=id;
      |             ~~~~~~^~~
#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...