Submission #780612

#TimeUsernameProblemLanguageResultExecution timeMemory
780612mousebeaverRarest Insects (IOI22_insects)C++17
74.07 / 100
107 ms456 KiB
#include <bits/stdc++.h> #include "insects.h" using namespace std; set<int> inside; set<int> outside; int types = -1; int countTypes() { while(inside.size() && press_button() > 1) { move_outside(*inside.begin()); outside.insert(*inside.begin()); inside.erase(inside.begin()); } vector<int> a(0); for(int i : outside) { a.push_back(i); } for(int i : a) { move_inside(i); inside.insert(i); outside.erase(i); if(inside.size() > 1) { if(press_button() > 1) { move_outside(i); outside.insert(i); inside.erase(i); } } } return inside.size(); } bool test(int k) //Every type at least k insects? { while(press_button() > k) { move_outside(*inside.begin()); outside.insert(*inside.begin()); inside.erase(inside.begin()); } vector<int> a(0); for(int i : outside) { a.push_back(i); } for(int i : a) { move_inside(i); inside.insert(i); outside.erase(i); if((int) inside.size() > k) { if(press_button() > k) { move_outside(i); outside.insert(i); inside.erase(i); } } } return((int) inside.size() == k*types); } int min_cardinality(int N) { for(int i = 0; i < N; i++) { outside.insert(i); } types = countTypes(); if(types <= 11) { while(inside.size()) { move_outside(*inside.begin()); outside.insert(*inside.begin()); inside.erase(inside.begin()); } vector<int> card(N, -1); for(int i = 0; i < N; i++) { if(card[i] == -1) { move_inside(i); vector<int> machine = {i}; for(int j = i+1; j < N; j++) { if(card[j] == -1) { move_inside(j); machine.push_back(j); int state = press_button(); if(state != (int) machine.size()) { move_outside(j); machine.pop_back(); } } } for(int j : machine) { card[j] = machine.size(); move_outside(j); } } } return *min_element(card.begin(), card.end()); } int left = 1; int right = N/types; while(left < right) { int mid = (left+right+1)/2; if(test(mid)) { left = mid; } else { right = mid-1; } } return left; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...