Submission #1215224

#TimeUsernameProblemLanguageResultExecution timeMemory
1215224dostsRarest Insects (IOI22_insects)C++20
53.15 / 100
51 ms4336 KiB
#include "insects.h" #include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") //#define int long long #define pii pair<int,int> #define vi vector<int> #define ff first #define ss second #define sp << " " << #define all(x) x.begin(),x.end() #define big(x) ((int)(x.size())) using namespace std; const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9; vi inside(LIM,0); int total = 0; void add(int p) { if (inside[p]) return; inside[p] = 1; total++; move_inside(p); } void remove(int p) { if (!inside[p]) return; inside[p] = 0; total--; move_outside(p); } int D = 0; vi placed; bool check(int N,int x) { placed.clear(); assert(total <= D*x); for (int i = 0;i<N;i++) { if (inside[i]) continue; placed.push_back(i); add(i); int y = press_button(); if (y > x) { placed.pop_back(); remove(i); } if (total == D*x) return true; } return (total == D*x); } int min_cardinality(int N) { for (int i = 0;i<N;i++) { add(i); int y = press_button(); if (y == 1) { D++; continue; } remove(i); } int l = 1; int r = N/D; while (l<=r) { int m = (l+r) >> 1; if (check(N,m)) l = m+1; else { for (auto it : placed) remove(it); r = m-1; } } return r; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...