Submission #73298

#	Time	Username	Problem	Language	Result	Execution time	Memory
73298		mr_banana	The Big Prize (IOI17_prize)	C++17	97.42 / 100	72 ms	2420 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>

using namespace std;
const int MN=200000+10,SQ=500;
bool mark[MN];
int a[2][MN];
void get(int x){
    if(mark[x]){
        return;
    }
    mark[x]=1;
    auto v=ask(x);
    a[0][x]=v[0],a[1][x]=v[1];
}
int numb(int x){
    return a[0][x]+a[1][x];
}
int numx;
void fnd(int l,int r,int ls,int mr){
    int num=numx-ls-mr;
    if(num==0){
        return;
    }
    if(r-l<1){
        return;
    }
    if(r-l<=num){
        for(int i=l;i<r;i++){
            get(i);
        }
        return;
    }
    int mid=(l+r)/2;
    while(mid<r){
        get(mid);
        if(numb(mid)<numx){
            mid++;
        }
        else{
            break;
        }
    }
    int mid1=(l+r)/2;
    if(mid==r){
        fnd(l,mid1,ls,mr+mid-mid1);
    }
    else{
        fnd(l,mid1,ls,a[1][mid]+mid-mid1);
        fnd(mid+1,r,a[0][mid],mr);
    }
}
int find_best(int n) {
	int mi=0;
	for(int i=0;i<SQ && i<n;i++){
        get(i);
        if(numb(i)>numb(mi)){
            mi=i;
        }
    }
    numx=numb(mi);
    fnd(0,n,0,0);
    for(int i=0;i<n;i++){
        if(mark[i] && a[0][i]+a[1][i]==0){
            return i;
        }
    }
	return 0;
}

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