제출 #430061

#제출 시각아이디문제언어결과실행 시간메모리
430061dreezy버섯 세기 (IOI20_mushrooms)C++17
0 / 100
21 ms532 KiB
#include <bits/stdc++.h> #include "mushrooms.h" using namespace std; #define pb push_back int geta(int l, int r){ if( l > r) return 0; if(l == r) return use_machine({0,l}) == 0; vector<int> inds; for(int i = l; i <=r; i++)inds.pb(i); int res = use_machine(inds); if(res == 0){ if(use_machine({0, l})== 0) return r - l + 1; else return 0; } else if(res == r -l){ if((r - l + 1)%2 == 0) return (r - l + 1)/2; else { if(use_machine({0,l}) == 0){ return (r - l + 1)/2 + 1; } else return (r - l + 1)/2; } } else if(res == 1){ int lo = l; int hi = r; int target = !use_machine({0, lo}); while(lo!= hi){ int mi = (lo + hi)/2; if( use_machine({0,mi}) == target){ hi = mi; } else{ lo = mi + 1; } } if(target == 1){//we were looking for the first B //cout << l <<", "<<r <<": "<<lo<<endl; return lo - l; } else{//we were looking for the first A return r - lo + 1; } } int mid = (l + r)/2; return geta( l, mid) + geta(mid + 1, r); } int count_mushrooms(int n) { return 1 + geta(1, n -1); } /************************/
#Verdict Execution timeMemoryGrader output
Fetching results...