Submission #431674

#	Time	Username	Problem	Language	Result	Execution time	Memory
431674		DanerZein	The Big Prize (IOI17_prize)	C++14	90 / 100	98 ms	1920 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){
      for(int j=18;j>=0;j--){
	if(id+(1<<j)<n){
	  int nid=id+(1<<j);
	  if(le[nid]==-1){
	    vector<int> aux=ask(nid);
	    le[nid]=aux[0]; ri[nid]=aux[1];
	    if(le[nid]==0 && ri[nid]==0) return nid;
	  }
	  if(le[nid]==le[id] && ri[nid]==ri[id]){
	    id=nid;
	  }
	}
      }
    }
    id++;
  }
}

Compilation message (stderr)

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

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