Submission #335669

#	Time	Username	Problem	Language	Result	Execution time	Memory
335669		couplefire	The Big Prize (IOI17_prize)	C++17	90 / 100	114 ms	512 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

int find_best(int n) {
    if(n == 1) return 0;
    int mx = 0;
	for(int i = 0; i<min(500, n); i++){
        vector<int> vv = ask(i);
        mx = max(mx, vv.front()+vv.back());
    }
    int cur = 0;
    for(int i = 0; i<mx; i++){
        int lo = cur, hi = n-1;
        while(lo < hi){
            int mid = lo+(hi-lo)/2;
            vector<int> vv = ask(mid);
            int a = vv.front(), b = vv.back();
            if(a+b < mx) hi = mid;
            else if(a == i) lo = mid+1;
            else hi = mid-1;
        }
        vector<int> vvv = ask(lo);
        if(vvv.front()+vvv.back() == 0) return lo;
        cur = lo+1; 
    }
	return 0;
}

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