Submission #447242

#TimeUsernameProblemLanguageResultExecution timeMemory
447242jwvg0425Chameleon's Love (JOI20_chameleon)C++17
24 / 100
64 ms344 KiB
#include "chameleon.h" #include <vector> using namespace std; vector<int> con[1005]; bool visit[1005]; bool answered[1005]; int l[1005]; vector<int> xs; vector<int> ys; int Query(int x, int s, int e) { vector<int> v = { xs[x] }; for (int i = s; i <= e; i++) v.push_back(ys[i]); return Query(v); } int Bisearch(int x, int l, int r, int d) { int lo = l, hi = r; int res = 0; while (lo <= hi) { int mid = (lo + hi) / 2; int q = Query(x, l, mid); int sz = mid - l + 2; if (q <= sz + d) { res = mid; hi = mid - 1; } else { lo = mid + 1; } } return res; } void Solve(int N) { for (int i = 1; i <= 2 * N; i++) { xs.push_back(i); if (Query(xs) != xs.size()) { xs.pop_back(); ys.push_back(i); } } xs.insert(xs.begin(), 0); ys.insert(ys.begin(), 0); int xl = (int)xs.size() - 1; int yl = (int)ys.size() - 1; for (int i = 1; i <= xl; i++) { if (Query(i, 1, yl) == yl) { auto x = Bisearch(i, 1, yl, -1); con[xs[i]] = { ys[x] }; con[ys[x]].push_back(xs[i]); continue; } auto b = Bisearch(i, 1, yl, -2); auto a = Bisearch(i, 1, b - 1, -1); con[ys[a]].push_back(xs[i]); con[ys[b]].push_back(xs[i]); if (Query(i, 1, a - 1) != a) { auto c = Bisearch(i, 1, a - 1, -1); con[xs[i]] = { ys[a], ys[b], ys[c] }; con[ys[c]].push_back(xs[i]); } else if (Query(i, a + 1, b - 1) != b - a) { auto c = Bisearch(i, a + 1, b - 1, -1); con[xs[i]] = { ys[a], ys[b], ys[c] }; con[ys[c]].push_back(xs[i]); } else { auto c = Bisearch(i, b + 1, yl, -1); con[xs[i]] = { ys[a], ys[b], ys[c] }; con[ys[c]].push_back(xs[i]); } } for (int i = 1; i <= 2 * N; i++) { if (visit[i]) continue; if (con[i].size() == 1) { Answer(i, con[i][0]); visit[i] = visit[con[i][0]] = true; answered[i] = answered[con[i][0]] = true; continue; } if (con[con[i][0]].size() == 1) { Answer(i, con[i][0]); visit[i] = visit[con[i][0]] = true; answered[i] = answered[con[i][0]] = true; } else if (con[con[i][1]].size() == 1) { Answer(i, con[i][1]); visit[i] = visit[con[i][1]] = true; answered[i] = answered[con[i][1]] = true; } else if (con[con[i][2]].size() == 1) { Answer(i, con[i][2]); visit[i] = visit[con[i][2]] = true; answered[i] = answered[con[i][2]] = true; } else { vector<int> a = { i, con[i][0], con[i][1] }; vector<int> b = { i, con[i][0], con[i][2] }; vector<int> c = { i, con[i][1], con[i][2] }; auto aq = Query(a); auto bq = Query(b); if (aq == 1) { visit[i] = true; l[i] = con[i][2]; } else if (bq == 1) { visit[i] = true; l[i] = con[i][1]; } else { visit[i] = true; l[i] = con[i][0]; } } } for (int i = 1; i <= 2 * N; i++) { if (answered[i]) continue; for (auto& c : con[i]) { if (c == l[i] || l[c] == i || answered[c]) continue; Answer(i, c); answered[i] = answered[c] = true; break; } } }

Compilation message (stderr)

chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:52:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   if (Query(xs) != xs.size())
      |       ~~~~~~~~~~^~~~~~~~~~~~
#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...