Submission #1215234

#TimeUsernameProblemLanguageResultExecution timeMemory
1215234dostsRarest Insects (IOI22_insects)C++20
0 / 100
16 ms4352 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; int zaten = 1; vi cand1; bool check(vi cand,int x) { if (x <= zaten) return true; vi placed; vi nono; for (auto it : cand) { add(it); placed.push_back(it); int y = press_button(); if (y > x) { nono.push_back(it); remove(it); placed.pop_back(); } } if (total == D*x) { zaten = x; cand1 = nono; return true; } cand1 = placed; return false; } int min_cardinality(int N) { for (int i = 0;i<N;i++) { add(i); int y = press_button(); if (y == 1) { D++; continue; } cand1.push_back(i); remove(i); } if (D == 1) return N; int l = 2; int r = N/D; while (l<=r) { int m = (l+r) >> 1; if (check(cand1,m)) l = m+1; else r = m-1; } return zaten; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...