제출 #831033

#제출 시각아이디문제언어결과실행 시간메모리
831033LIF커다란 상품 (IOI17_prize)C++14
97.82 / 100
56 ms1924 KiB
#include "prize.h" #include<bits/stdc++.h> using namespace std; int ll[300005]; int rr[300005]; int maxn = -1; vector<int> ans; int last = -1; void find(int l,int r,int nowsize) { if(l == r) { ans.push_back(l); return; } bool flag = true; while(l <= r) { if(ll[l] == -1) { vector<int> temp = ask(l); ll[l] = temp[0];rr[l] = temp[1]; if(ll[l] + rr[l] == maxn)break; else { //if(ll[l] + rr[l] == 0)last = l; ans.push_back(l); l++; } } else { if(ll[l] + rr[l] == maxn)break; else { ans.push_back(l); l++; } } } while(l <= r) { if(rr[r] == -1) { vector<int> temp = ask(r); ll[r] = temp[0];rr[r] = temp[1]; if(ll[r] + rr[r] == maxn)break; else { ans.push_back(r); r--; } } else { if(ll[r] + rr[r] == maxn)break; else { ans.push_back(r); r--; } } } if(l > r)return; int mid1 = (l+r)>>1; int mid2 = (l+r)>>1; while(mid1 >= l) { if(rr[mid1] == -1) { vector<int> temp = ask(mid1); ll[mid1] = temp[0];rr[mid1] = temp[1]; if(ll[mid1] + rr[mid1] == maxn)break; else { ans.push_back(mid1); mid1--; } } else { if(ll[mid1] + rr[mid1] == maxn)break; else { ans.push_back(mid1); mid1--; } } } int xx = ll[mid1] - ll[l]; if(xx != 0)find(l,mid1,xx); while(mid2 <= r) { if(ll[mid2] == -1) { vector<int> temp = ask(mid2); ll[mid2] = temp[0];rr[mid2] = temp[1]; if(ll[mid2] + rr[mid2] == maxn)break; else { ans.push_back(mid2); mid2++; } } else { if(ll[mid2] + rr[mid2] == maxn)break; else { ans.push_back(mid2); mid2++; } } } xx = ll[r] - ll[mid2]; if(xx!=0)find(mid2,r,xx); return; } int find_best(int n) { srand(time(0)); for(int i=0;i<n;i++)ll[i] = -1; for(int i=0;i<n;i++)rr[i] = -1; int first = 0; int xx = 480; for(int pp=0;pp<xx;pp++) { int i = rand() % n; vector<int> a = ask(i); int su = a[0] + a[1]; ll[i] = a[0];rr[i] = a[1]; if(su == 0)return i; if(su > maxn) { maxn = su; first = i; } } find(0,first-1,ll[first]); find(first+1,n-1,rr[first]); for(int i=0;i<ans.size();i++) { if(ll[ans[i]] +rr[ans[i]] == 0)return ans[i]; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

prize.cpp: In function 'void find(int, int, int)':
prize.cpp:16:7: warning: unused variable 'flag' [-Wunused-variable]
   16 |  bool flag = true;
      |       ^~~~
prize.cpp: In function 'int find_best(int)':
prize.cpp:143:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |  for(int i=0;i<ans.size();i++)
      |              ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...