Submission #1029086

#TimeUsernameProblemLanguageResultExecution timeMemory
102908642kangarooRarest Insects (IOI22_insects)C++17
99.82 / 100
42 ms1004 KiB
#include "insects.h" #include "bits/stdc++.h" using namespace std; int min_cardinality(int N) { set<int> inside, outside, aIn; for (int i = 0; i < N; ++i) { move_inside(i); if (press_button() > 1) { if (i == N - 1) { aIn.insert(i); } else { outside.insert(i); move_outside(i); } } else { inside.insert(i); } } int k = inside.size(); int l = 1, r = N / k + 1; while (l + 1 < r) { int m = (l + r + 1) / 2; set<int> nIn, nOut; for (auto e: outside) { if ((inside.size() + nIn.size() + aIn.size()) == m * k) { nOut.insert(e); } else { move_inside(e); if (press_button() > m) { nOut.insert(e); move_outside(e); } else nIn.insert(e); } } if ((inside.size() + nIn.size() + aIn.size()) == m * k) { l = m; outside = nOut; inside.insert(nIn.begin(), nIn.end()); inside.insert(aIn.begin(), aIn.end()); aIn.clear(); } else { r = min(m, (int)(inside.size() + nIn.size() + aIn.size())/k + 1); int nM = (l + r + 1) / 2 - l; nIn.insert(aIn.begin(), aIn.end()); aIn.clear(); for (int i = 0; i < nM && !nIn.empty(); ++i) { aIn.insert(*nIn.begin()); nIn.erase(nIn.begin()); } for (auto e: nIn) { move_outside(e); } outside = nIn; } } return l; }

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:27:50: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |    if ((inside.size() + nIn.size() + aIn.size()) == m * k) {
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
insects.cpp:37:49: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |   if ((inside.size() + nIn.size() + aIn.size()) == m * k) {
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...