Submission #230617

#TimeUsernameProblemLanguageResultExecution timeMemory
230617wilwxkChameleon's Love (JOI20_chameleon)C++14
0 / 100
76 ms512 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; void dfs(int u) { for(auto v : ans[u]) { if(color[v] != -1) continue; color[v] = color[u]^1; dfs(v); } } 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; dfs(i); } comp[0].clear(); comp[1].clear(); for(int i = 1; i <= k; i++) comp[color[i]].push_back(i); } void Solve(int N) { n = 2*N; comp[0].push_back(1); for(int u = 2; u <= n; u++) { separate(u-1); // for(int a : comp[0]) printf("%d ", a); cout << endl; // for(int a : comp[1]) printf("%d ", a); cout << endl; for(int k = 0; k < 2; k++) { int aa = -1, bb = comp[k].size(), cc = -1; vector<int> qv; for(int j = LOGN; j >= 0; j--) { int ind = aa + (1<<j); if(ind >= comp[k].size()) continue; qv.clear(); for(int i = 0; i <= ind; i++) qv.push_back(comp[k][i]); qv.push_back(u); if(Query(qv) == qv.size()) aa = ind; } for(int j = LOGN; j >= 0; j--) { int ind = bb - (1<<j); if(ind < 0) continue; qv.clear(); for(int i = ind; i < comp[k].size(); i++) qv.push_back(comp[k][i]); qv.push_back(u); if(Query(qv) == qv.size()) bb = ind; } cc = aa+1; for(int j = LOGN; j >= 0; j--) { int ind = cc + (1<<j); if(ind >= bb-1) continue; qv.clear(); for(int i = aa+2; i <= ind; i++) qv.push_back(comp[k][i]); qv.push_back(u); if(Query(qv) == qv.size()) cc = ind; } // printf("%d: abc %d %d %d\n", u, aa, bb, cc); if(aa+1 < cc+1 && cc+1 < bb-1 && Query({u, comp[k][cc+1]}) != 2) { cc = comp[k][cc+1]; ans[cc].push_back(u); ans[u].push_back(cc); // printf("connect %d %d\n", u, cc); } if(aa+1 < comp[k].size() && aa+1 != bb-1 && Query({u, comp[k][aa+1]}) != 2) { aa = comp[k][aa+1]; ans[aa].push_back(u); ans[u].push_back(aa); // printf("connect %d %d\n", u, aa); } if(bb-1 >= 0 && Query({u, comp[k][bb-1]}) != 2) { bb = comp[k][bb-1]; ans[bb].push_back(u); ans[u].push_back(bb); // printf("connect %d %d\n", u, bb); } } } for(int u = 1; u <= n; u++) { if(color[u] == 2) continue; if(ans[u].size() == 1) { Answer(u, ans[u][0]); color[u] = color[ans[u][0]] = 2; } 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; // 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 'void Solve(int)':
chameleon.cpp:51:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(ind >= comp[k].size()) continue;
        ~~~~^~~~~~~~~~~~~~~~~
chameleon.cpp:55:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(Query(qv) == qv.size()) aa = ind;
        ~~~~~~~~~~^~~~~~~~~~~~
chameleon.cpp:62:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = ind; i < comp[k].size(); i++) qv.push_back(comp[k][i]);
                      ~~^~~~~~~~~~~~~~~~
chameleon.cpp:64:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(Query(qv) == qv.size()) bb = ind;
        ~~~~~~~~~~^~~~~~~~~~~~
chameleon.cpp:74:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(Query(qv) == qv.size()) cc = ind;
        ~~~~~~~~~~^~~~~~~~~~~~
chameleon.cpp:85:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(aa+1 < comp[k].size() && aa+1 != bb-1 && Query({u, comp[k][aa+1]}) != 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...