Submission #757215

#	Time	Username	Problem	Language	Result	Execution time	Memory
757215		alexander707070	The Big Prize (IOI17_prize)	C++14	95.76 / 100	59 ms	344 KiB

prize

#include<bits/stdc++.h>
#include "prize.h"
#define MAXN 200007
using namespace std;
 
int nn,r,res;
vector<int> w;

int solve(int l,int r,int reml,int remr){
    if(l>r)return 0;

    int mid=(l+r)/2,p;
    vector<int> curr;

    while(mid<=r){
        curr=ask(mid);
        if(curr[0]+curr[1]==res)break;
        if(curr[0]+curr[1]==0)return mid;
        mid++;
    }

    if(mid==r+1){
        mid=(l+r)/2-1;

        while(mid>=l){
            curr=ask(mid);
            if(curr[0]+curr[1]==res)break;
            if(curr[0]+curr[1]==0)return mid;
            mid--;
        }

        if(mid==l-1)return 0;

        curr[0]-=reml;
        if(curr[0]>0){
            return solve(l,mid-1,reml,remr+(r-mid));
        }

        return 0;
    }else{
        curr[0]-=reml-(mid-(l+r)/2);
        curr[1]-=remr;

        if(curr[0]>0){
            p=solve(l,(l+r)/2-1,reml,remr+curr[1]+(mid-(l+r)/2));
            if(p!=0)return p;
        }
        if(curr[1]>0){
            p=solve(mid+1,r,reml+curr[0]+(mid-(l+r)/2),remr);
            if(p!=0)return p;
        }

        return 0;
    }

    return 0;
}

int find_best(int N){
    nn=N;
    for(int i=1;i<=700;i++){
        r=rand()%nn; w=ask(r);
        res=max(res,w[0]+w[1]);
    }

    return solve(0,nn-1,0,0);
}

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