제출 #132102

#제출 시각아이디문제언어결과실행 시간메모리
132102MoNsTeR_CuBe커다란 상품 (IOI17_prize)C++17
20 / 100
154 ms44852 KiB
#include <bits/stdc++.h> #include "prize.h" using namespace std; vector< vector< int > > memo; int TOT = 0; vector< int > ASK(int a){ if(memo[a][0] != -1) return memo[a]; else{ TOT++; assert(TOT < 10000); return memo[a] = ask(a); } } int find_best(int n) { int poppy_index = -1; int poppy_tot = 0; vector< vector< int > > rem(n+1, vector< int > (2)); memo.resize(n, vector< int >(2,-1)); for(int i = 0; i < min(n,460); i++){ vector< int > query = ASK(i); rem[query[0] + query[1]] = query; if(query[0] + query[1] >= poppy_tot){ poppy_tot = query[0] + query[1]; poppy_index = i; }else if(query[0] + query[1] == 0){ return i; } } int curr = poppy_index+1; while(curr < n){ vector< int > query = ASK(curr); rem[query[0] + query[1]] = query; if(query[0] + query[1] == 0) return curr; while(query[0] + query[1] != poppy_tot){ curr++; query = ASK(curr); rem[query[0] + query[1]] = query; if(query[0] + query[1] == 0) return curr; } int left = curr+1; int right = n-1; while(left < right){ int mid = (left+right)/2; vector< int > Q = ASK(mid); if(Q[0] + Q[1] == 0) return mid; if(Q[0] + Q[1] == poppy_tot && Q[0] - query[0] == 0){ left = mid+1; rem[Q[0] + Q[1]] = Q; } else if(Q[0] + Q[1] == poppy_tot && Q[0] - query[0] > 0) right = mid-1; else if(Q[0] + Q[1] != poppy_tot && Q[0] - rem[Q[0] + Q[1]][0] == 0){ left = mid+1; rem[Q[0] + Q[1]] = Q; } else right = mid; } curr = left; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...