제출 #668894

#제출 시각아이디문제언어결과실행 시간메모리
668894a_aguilo커다란 상품 (IOI17_prize)C++14
90 / 100
61 ms1992 KiB
#include "prize.h" #include<bits/stdc++.h> using namespace std; int N; vector<int> LeftVal, RightVal; int binarySearch(int left, int right, int leftLollipop, int rightLollipop){ int ans = -1; if(left+1 >= right) return -1; int mid = left + (right - left)/2; vector<int> trial = ask(mid); LeftVal[mid] = trial[0]; RightVal[mid] = trial[1]; if((trial[0] +trial[1]) == 0) return mid; int myRight = mid; int myLeft = mid; while((LeftVal[myLeft] + RightVal[myLeft]) < (LeftVal[leftLollipop] + RightVal[leftLollipop])){ myLeft--; trial = ask(myLeft); LeftVal[myLeft] = trial[0]; RightVal[myLeft] = trial[1]; if((trial[0]+trial[1]) == 0) return myLeft; } while(((LeftVal[myRight] + RightVal[myRight]) < (LeftVal[leftLollipop] + RightVal[leftLollipop])) and (myRight < right)){ myRight++; trial = ask(myRight); LeftVal[myRight] = trial[0]; RightVal[myRight] = trial[1]; if((trial[0]+trial[1]) == 0) return myRight; } if((LeftVal[myLeft] - LeftVal[leftLollipop]) > 0) ans = max(ans, binarySearch(left, myLeft, leftLollipop, myLeft)); if(myRight < right){ if(right == N){ if(RightVal[myRight] > 0) ans = max(ans, binarySearch(myRight, right, myRight, rightLollipop)); } else{ if((RightVal[myRight] - RightVal[rightLollipop])> 0) ans = max(ans, binarySearch(myRight, right, myRight, rightLollipop)); } } return ans; } int find_best(int n) { N = n; LeftVal = vector<int>(n, -1); RightVal = vector<int>(n, -1); vector<int> trial = ask(0); int lollipop = 0; LeftVal[0] = trial[0]; RightVal[0] = trial[1]; if((LeftVal[0] + RightVal[0]) == 0) return 0; for(int i = 1; i < min(n, 500); ++i){ trial = ask(i); LeftVal[i] = trial[0]; RightVal[i] = trial[1]; if((LeftVal[i]+RightVal[i]) >= (LeftVal[lollipop] + RightVal[lollipop])) lollipop = i; if((LeftVal[i] + RightVal[i]) == 0) return i; } return binarySearch(499, n, lollipop, n); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...