Submission #1207899

#TimeUsernameProblemLanguageResultExecution timeMemory
1207899HappyCapybaraRarest Insects (IOI22_insects)C++17
100 / 100
14 ms424 KiB
#include "insects.h" #include<bits/stdc++.h> using namespace std; int min_cardinality(int N){ random_device rd; mt19937 g(rd()); vector<bool> in(N, false); int t = 0; for (int i=0; i<N; i++){ move_inside(i); in[i] = true; t++; if (press_button() > 1){ move_outside(i); in[i] = false; t--; } } if (t == 1) return N; int k = t; int l = 1, r = N/t+1; vector<int> w; for (int i=0; i<N; i++) w.push_back(i); while (l < r-1){ shuffle(w.begin(), w.end(), g); vector<int> v; int m = (l+r)/2; for (int j=0; j<w.size(); j++){ if (k == t*m) break; int i = w[j]; if (in[i]) continue; move_inside(i); in[i] = true; k++; if (press_button() > m){ move_outside(i); in[i] = false; k--; } else v.push_back(i); } if (k == t*m) l = m; else { r = m; for (int x : v){ move_outside(x); in[x] = false; k--; } w = v; } } return l; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...