Submission #1075190

#TimeUsernameProblemLanguageResultExecution timeMemory
1075190ZicrusRarest Insects (IOI22_insects)C++17
69.26 / 100
92 ms708 KiB
#include <bits/stdc++.h> #include "insects.h" using namespace std; typedef long long ll; int n; vector<bool> in; unordered_set<int> s; int cnt; int add(int i) { if (in[i]) return 0; move_inside(i); cnt++; in[i] = true; return 1; } int remove(int i) { if (!in[i]) return 0; move_outside(i); cnt--; in[i] = false; return 1; } int min_cardinality(int N) { n = N; cnt = 0; mt19937 mt(time(0)); in = vector<bool>(n); for (int i = 0; i < n; i++) { add(i); } int mx = press_button(); int prevSz = cnt; while (mx > 1) { int cur = mx; while (cur == mx) { int i = mt()%n; while (!remove(i)) i = mt()%n; int j = mt()%n; while (!remove(j)) j = mt()%n; cur = press_button(); if (cur == mx) { s.insert(i); s.insert(j); } else { add(j); cur = press_button(); if (cur == mx) { s.insert(i); remove(j); } cur = mx-1; } } vector<int> s0; for (auto &e : s) { s0.push_back(e); } shuffle(s0.begin(), s0.end(), mt); for (int i = 0; i < s0.size(); i++) { if (i == s0.size()-1) { if (add(s0[i])) { cur = press_button(); if (cur == mx) remove(s0[i]); } continue; } add(s0[i]); add(s0[i+1]); cur = press_button(); if (cur == mx) { remove(s0[i+1]); cur = press_button(); if (cur == mx) { remove(s0[i]); } else { i++; } } } if (cnt * mx % (mx-1) == 0 && cnt * mx / (mx-1) == prevSz) { break; } s.clear(); prevSz = cnt; mx--; } return mx; } #ifdef TEST #include "grader.cpp" #endif

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:65:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for (int i = 0; i < s0.size(); i++) {
      |                         ~~^~~~~~~~~~~
insects.cpp:66:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             if (i == s0.size()-1) {
      |                 ~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...