Submission #797746

#TimeUsernameProblemLanguageResultExecution timeMemory
797746HaroldVemenoRarest Insects (IOI22_insects)C++17
99.78 / 100
54 ms296 KiB
#include "insects.h" #include <bits/stdc++.h> #ifdef GUDEB #define D(x) cerr << #x << ": " << (x) << '\n'; #define ifdeb if(true) #else #define D(x) ; #define ifdeb if(false) #endif #define all(x) begin(x), end(x) using namespace std; using ull = unsigned long long; using ll = long long; // #define int ll; int min_cardinality(int n) { vector<bool> skip(n); vector<bool> box(n); int s = 0; for(int i = 0; i < n; ++i) { box[i] = true; move_inside(i); ++s; int c = press_button(); if(c > 1) { move_outside(i); --s; box[i] = false; } } D(s) if(s == n) return 1; for(int i = 0; i < n; ++i) { if(box[i]) { move_outside(i); skip[i] = true; } } int rm = 1; int f = 1; int t = n/s; while(f != t) { int m = (f+t+1)/2; D(f) D(t) D(m) int ss = 0; for(int i = 0; i < n; ++i) { if(skip[i]) continue; box[i] = true; ++ss; move_inside(i); int c = press_button(); if(c > m-rm) { move_outside(i); box[i] = false; --ss; } } D(ss) if(ss == s*(m-rm)) { rm = m; f = m; for(int i = 0; i < n; ++i) { if(box[i]) skip[i] = true; } } else { t = m-1; for(int i = 0; i < n; ++i) { if(!box[i]) skip[i] = true; } } for(int i = 0; i < n; ++i) { if(box[i]) move_outside(i); box[i] = false; } } return f; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...