제출 #430098

#제출 시각아이디문제언어결과실행 시간메모리
430098dreezy버섯 세기 (IOI20_mushrooms)C++17
0 / 100
1096 ms1566788 KiB
#include <bits/stdc++.h> #include "mushrooms.h" using namespace std; #define pb push_back #define mp make_pair vector<vector<int>> queries; int use(int l, int r){ if(queries[l][r]!= -1) return queries[l][r]; vector<int> q; if(l != 0) for(int i =l; i<=r; i++) q.pb(i); else q.pb(0), q.pb(r); int res = use_machine(q); queries[l][r] = res; return res; } int geta(int l, int r){ if( l > r) return 0; if(l == r) return use(0,l) == 0; vector<int> inds; int res = use(l, r); if(res == 0){ if(use(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(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(0,lo); while(lo!= hi){ int mi = (lo + hi)/2; if( use(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) { queries.assign(n, vector<int>(n, -1)); int ans = 1; int blcksz =100; for(int block = 1; block <n; block += blcksz){ ans += geta(block, min(blcksz + block -1 , n -1) ); } return ans; } /************************/
#Verdict Execution timeMemoryGrader output
Fetching results...