제출 #1062150

#제출 시각아이디문제언어결과실행 시간메모리
1062150jerzyk드문 곤충 (IOI22_insects)C++17
53.16 / 100
113 ms2744 KiB
#include <bits/stdc++.h> #include "insects.h" using namespace std; #define pb push_back #define st first #define nd second typedef long long ll; typedef long double ld; const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL; const int II = 2 * 1000 * 1000 * 1000; const ll M = 1000LL * 1000LL * 1000LL + 7LL; const int N = 1000 * 1000 + 7; bool out[N], czy[N], wh[N]; vector<int> cur; int lft, dif; int findDif(int n) { for(int i = 0; i < n; ++i) { move_inside(i); cur.pb(i); if(press_button() > 1) { cur.pop_back(); move_outside(i); } } int ans = cur.size(); for(int i = 0; i < (int)cur.size(); ++i) { out[cur[i]] = true; move_outside(cur[i]); } cur.clear(); return ans; } int Check(int x, int n) { int ans = 0, xd = 0; for(int i = 0; i < n; ++i) { wh[i] = false; if(out[i]) continue; move_inside(i); czy[i] = true; ans = press_button(); ++xd; if(ans > x + 1) { --xd; --ans; wh[i] = true; czy[i] = false; move_outside(i); } } //cerr << "xddd " << x << " " << " " << xd << " " << ans << " " << lft << "\n"; if(xd == dif * (x + 1)) ans = x + 1; else ans = min(ans, x); for(int i = 0; i < n; ++i) { if(out[i]) continue; if(czy[i]) move_outside(i); czy[i] = false; } if(ans == x + 1) return ans; for(int i = 0; i < n; ++i) if(wh[i]) { --lft; out[i] = true; } return ans; } int BS(int maks, int n) { int p = 0, k = maks; while(p < k) { int s = (p + k) / 2; if(dif == 1) return lft; int x = Check(s, n); if(x > s) p = s + 1; else k = s; k = min(k, lft); } return p; } int min_cardinality(int n) { dif = findDif(n); lft = n - dif; //cerr << "dif " << dif << "\n"; int m = lft / dif; int ans = BS(m, n); return ans + 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...