Submission #206577

#	Time	Username	Problem	Language	Result	Execution time	Memory
206577		anonymous	The Big Prize (IOI17_prize)	C++14	100 / 100	60 ms	9980 KiB

prize

#include "prize.h"
#include<vector>
#include<map>
#include<utility>
#include<cassert>
#define MAXN 200005
using namespace std;
map<int, int> Q[MAXN];
int slv(int l, int r) {
    if (l > r) {return(-1);}
    int mid = (l + r) >> 1;
    vector<int> res = ask(mid);
    int tot = res[0] + res[1], resL=-1, resR=-1;
    if (tot == 0) {return(mid);}
    else if (l == r) {return(-1);}
    auto ptr1 = Q[tot].insert({mid, res[0]}).first, ptr2=ptr1;
    if ((ptr1 == Q[tot].begin() || (*(--ptr1)).second != res[0]) && res[0]) {
        resL = slv(l, mid-1);
        if (resL >= 0) {return(resL);}
    }
    if (((++ptr2) == Q[tot].end() || (*ptr2).second != res[0]) && res[1]) {
        resR = slv(mid+1, r);
        if (resR >= 0) {return(resR);}
    }
    return(-1);
}

int find_best(int n) {
	return(slv(0, n-1));
}

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