Submission #1029090

#TimeUsernameProblemLanguageResultExecution timeMemory
102909042kangarooRarest Insects (IOI22_insects)C++17
25 / 100
39 ms1280 KiB
#include "insects.h" #include "bits/stdc++.h" using namespace std; int min_cardinality(int N) { int nums = 0; set<int> inside, outside, aIn; for (int i = 0; i < N; ++i) { nums++; 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 { nums++; 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; } } if ((double)nums/(double)N > 3) return k; return l; }

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:29:50: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |    if ((inside.size() + nIn.size() + aIn.size()) == m * k) {
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
insects.cpp:40:49: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |   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...