Submission #629610

#TimeUsernameProblemLanguageResultExecution timeMemory
629610flashmtRarest Insects (IOI22_insects)C++17
99.95 / 100
63 ms440 KiB
#include <bits/stdc++.h> #include "insects.h" using namespace std; pair<vector<int>, vector<int>> findFirstOccurrences(vector<int> id, int maxC, int expectedSize) { vector<int> good, bad; for (int i : id) { if (size(good) == expectedSize) { bad.push_back(i); continue; } move_inside(i); if (press_button() <= maxC) good.push_back(i); else { move_outside(i); bad.push_back(i); } } for (int i : good) move_outside(i); return {good, bad}; } int min_cardinality(int n) { vector<int> id(n); iota(begin(id), end(id), 0); auto [good, bad] = findFirstOccurrences(id, 1, n); int typeCnt = size(good); int ans = 1; id = bad; while (size(id) >= typeCnt) { int low = 1, high = size(id) / typeCnt; int mid = (low + high) / 2; int expectedSize = typeCnt * mid; tie(good, bad) = findFirstOccurrences(id, mid, expectedSize); if (size(good) < expectedSize) id = good; else { ans += mid; id = bad; } } return ans; }

Compilation message (stderr)

insects.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > findFirstOccurrences(std::vector<int>, int, int)':
insects.cpp:10:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   10 |     if (size(good) == expectedSize)
      |         ~~~~~~~~~~~^~~~~~~~~~~~~~~
insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:38:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |   while (size(id) >= typeCnt)
      |          ~~~~~~~~~^~~~~~~~~~
insects.cpp:44:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |     if (size(good) < expectedSize) id = good;
      |         ~~~~~~~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...