Submission #699536

#TimeUsernameProblemLanguageResultExecution timeMemory
699536MasterTasterThe Big Prize (IOI17_prize)C++14
93.03 / 100
56 ms2168 KiB
#include "prize.h" #include <iostream> #include <vector> #include <cmath> #define ll long long #define pii pair<int, int> #define xx first #define yy second #define pb push_back #define MAXN 200010 using namespace std; int n, l[MAXN], r[MAXN], maxx, ret=-1, sq=480; vector<int> all; /*bool check(int i, int k) { vector<int> p=ask(i); int le=p[0], ri=p[1]; if ((le+ri)<maxx) return true; if (le>k) return true; return false; }*/ bool vis[MAXN]; void askk(int i) { if (i==-1) return; if (i==n) { l[i]=maxx; return; } if (!vis[i]) { vector<int> p=ask(i); l[i]=p[0]; r[i]=p[1]; vis[i]=true; } } void ch() { askk(all[all.size()-1]); if ((l[all[all.size()-1]]+r[all[all.size()-1]])==0) ret=all[all.size()-1]; } void solve(int left, int right) { if (ret!=-1) return; int mid=left+(right-left)/2; if (left>right) return; askk(mid); if (left==right) { /*if ((l[mid]+r[mid])<maxx)*/ all.pb(mid); ch(); return; } /*if (left==(right-1)) { if ((l[mid]+r[mid])<maxx) { all.pb(mid); ch(); if (ret!=-1) return; } mid++; askk(mid); if ((l[mid]+r[mid])<maxx) { all.pb(mid); ch(); } return; }*/ if ((l[mid]+r[mid])<maxx) { all.pb(mid); ch(); if (ret!=-1) return; askk(left-1); askk(right+1); int pom; if (left==0) pom=0; else pom=l[left-1]; if (l[mid]-pom) solve(left, mid-1); if (l[right+1]-l[mid]) solve(mid+1, right); } else { askk(left-1); askk(right+1); int pom; if (left==0) pom=0; else pom=l[left-1]; if (l[mid]-pom) solve(left, mid-1); if (l[right+1]-l[mid]) solve(mid+1, right); } } int find_best(int N) { n=N; sq=min(sq, n-1);//2*sqrt(n); for (int i=0; i<=sq; i++) { askk(i); if (l[i]+r[i]==0) return i; maxx=max(maxx, l[i]+r[i]); } int left=0, right=n-1; solve(left, right); /*int ret=0; for (int i=0; i<all.size(); i++) { askk(all[i]); if ((l[all[i]]+r[all[i]])==0) ret=all[i]; }*/ return ret; } ///1, 2, 5, 26, 677 /* 8 3 2 3 1 3 3 2 3 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...