제출 #629158

#제출 시각아이디문제언어결과실행 시간메모리
629158flashmt드문 곤충 (IOI22_insects)C++17
68.91 / 100
127 ms452 KiB
#include <bits/stdc++.h> #include "insects.h" using namespace std; pair<vector<int>, vector<int>> findFirstOccurrences(vector<int> id, int maxC) { vector<int> good, bad; for (int i : id) { 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 solveSmallTypeCount(int n, vector<int> occurrences) { int typeCnt = size(occurrences); vector<int> cnt(typeCnt, 1); for (int i = 0; i < n; i++) { if (find(begin(occurrences), end(occurrences), i) != end(occurrences)) continue; move_inside(i); int found = 0; for (int j = 1; j < size(occurrences); j++) { int cur = occurrences[j]; move_inside(cur); if (press_button() == 2) { found = j; move_outside(cur); break; } move_outside(cur); } move_outside(i); cnt[found]++; } return *min_element(begin(cnt), end(cnt)); } int min_cardinality(int n) { vector<int> id(n); iota(begin(id), end(id), 0); auto [good, bad] = findFirstOccurrences(id, 1); int typeCnt = size(good); if (typeCnt <= 8) return solveSmallTypeCount(n, good); int low = 2, high = n / typeCnt, ans = 1; id = bad; while (low <= high) { int mid = (low + high) / 2; tie(good, bad) = findFirstOccurrences(id, mid - ans); if (size(good) == typeCnt * (mid - ans)) { ans = mid; low = mid + 1; id = bad; } else { high = mid - 1; id = good; } } return ans; }

컴파일 시 표준 에러 (stderr) 메시지

insects.cpp: In function 'int solveSmallTypeCount(int, std::vector<int>)':
insects.cpp:34:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int j = 1; j < size(occurrences); j++)
      |                     ~~^~~~~~~~~~~~~~~~~~~
insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:68:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |     if (size(good) == typeCnt * (mid - ans))
      |         ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...