Submission #230631

#TimeUsernameProblemLanguageResultExecution timeMemory
230631wilwxkChameleon's Love (JOI20_chameleon)C++14
0 / 100
4 ms384 KiB
#include <bits/stdc++.h> #include "chameleon.h" using namespace std; const int MAXN = 1005; const int LOGN = 9; int color[MAXN]; vector<int> bad[MAXN], ans[MAXN]; vector<int> comp[2]; int n; int dfs(int u) { int cnt = color[u]; for(auto v : ans[u]) { if(color[v] != -1) continue; color[v] = color[u]^1; cnt += dfs(v); } return cnt; } void separate(int k) { for(int i = 1; i <= k; i++) color[i] = -1; for(int i = 1; i <= k; i++) { if(color[i] != -1) continue; color[i] = 0; int a = dfs(i); color[i] = 1; int b = dfs(i); if(a > b) { color[i] = 0; dfs(i); } } comp[0].clear(); comp[1].clear(); for(int i = 1; i <= k; i++) comp[color[i]].push_back(i); } int bsearch(int u, int k, int l, int r) { if(l >= r) return l; int x = l; vector<int> qv; for(int j = LOGN; j >= 0; j--) { int ind = x + (1<<j); if(ind > r) continue; qv.clear(); for(int i = l+1; i <= ind; i++) qv.push_back(comp[k][i]); qv.push_back(u); // for(auto a : qv) printf("%d ", a); cout << endl; // printf("q %d / %d %d %d %d\n", ind, u, k, l, r); if(Query(qv) == qv.size()) x = ind; } return x; } void Solve(int N) { n = 2*N; comp[0].push_back(1); for(int u = 2; u <= n; u++) { separate(u-1); int cnt = 0; for(int k = 0; k < 2; k++) { int l = -1; int r = comp[k].size()-1; for(int kk = 0; kk < 3; kk++) { if(cnt == 3) break; int ind = bsearch(u, k, l, r); if(ind == r) break; ans[u].push_back(comp[k][ind+1]); ans[comp[k][ind+1]].push_back(u); // printf("connect %d %d\n", u, comp[k][ind+1]); cnt++; l = ind+1; } } } for(int u = 1; u <= n; u++) { if(ans[u].size() == 1) continue; else { if(Query({u, ans[u][0], ans[u][1]}) == 1) { bad[ans[u][2]].push_back(u); bad[u].push_back(ans[u][2]); } else if(Query({u, ans[u][1], ans[u][2]}) == 1) { bad[ans[u][0]].push_back(u); bad[u].push_back(ans[u][0]); } else { bad[ans[u][1]].push_back(u); bad[u].push_back(ans[u][1]); } } } for(int u = 1; u <= n; u++) { if(color[u] == 2) continue; int x; if(ans[u].size() == 1) { x = ans[u][0]; } else { for(int k = 0; k < 3; k++) { if(ans[u][k] != bad[u][0] && ans[u][k] != bad[u][1]) { x = ans[u][k]; } } } Answer(u, x); color[u] = color[x] = 2; } }

Compilation message (stderr)

chameleon.cpp: In function 'int bsearch(int, int, int, int)':
chameleon.cpp:53:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(Query(qv) == qv.size()) x = ind;
      ~~~~~~~~~~^~~~~~~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:123:23: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   color[u] = color[x] = 2;
              ~~~~~~~~~^~~
#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...