Submission #431658

#	Time	Username	Problem	Language	Result	Execution time	Memory
431658		DanerZein	The Big Prize (IOI17_prize)	C++14	90 / 100	96 ms	1896 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
const int MAX_N=2e5;
int le[MAX_N],ri[MAX_N];
int find_best(int n) {
  int ma=-1;
  int id=0;
  memset(le,-1,sizeof le); memset(ri,-1,sizeof ri);
  for(int i=0;i<min(500,n);i++){
    vector<int> aux=ask(i);
    le[i]=aux[0]; ri[i]=aux[1];
    if(le[i]==0 && ri[i]==0) return i;
    ma=max(ma,le[i]+ri[i]);
  }
  while(id!=n){
    if(le[id]==-1){
      vector<int> aux=ask(id);
      le[id]=aux[0]; ri[id]=aux[1];
    }
    if(le[id]==0 && ri[id]==0) return id;
    if(le[id]+ri[id]==ma){
      int l=id,r=n;
      while(r-l>1){
	int mid=(l+r)/2;
	if(le[mid]==-1){
	  vector<int>  aux=ask(mid);
	  le[mid]=aux[0]; ri[mid]=aux[1];
	  if(le[mid]==0 && ri[mid]==0) return mid;
	}
	if(le[mid]==le[id] && ri[mid]==ri[id]){
	  l=mid;
	}
	else r=mid;
      }
      id=l;
    }
    id++;
  }
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:41:1: warning: control reaches end of non-void function [-Wreturn-type]
   41 | }
      | ^

• Subtask 1: 20 / 20
• Subtask 2: 70 / 80