Submission #828226

#	Time	Username	Problem	Language	Result	Execution time	Memory
828226		tolbi	The Big Prize (IOI17_prize)	C++17	100 / 100	51 ms	896 KiB

prize

#include <bits/stdc++.h>
using namespace std;
#include "prize.h"
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
int ans = -1;
map<int,vector<int>> mp;
inline vector<int> query(int x){
    if (mp.count(x)) return mp[x];
    return mp[x]=ask(x);
}
inline int querys(int x){
    return query(x)[0]+query(x)[1];
}
void solve(int l, int r){
    if (l==r){
        if (querys(l)==0) ans=l;
        return;
    }
    if (querys(l)<querys(r)){
        if (querys(l)==0){
            ans=l;
            return;
        }
        solve(l+1,r);
        return;
    }
    else if (querys(r)<querys(l)){
        if (querys(r)==0){
            ans=r;
            return;
        }
        solve(l,r-1);
        return;
    }
    if (query(l)[0]==query(r)[0]) return;
    int mid = l+(r-l)/2;
    solve(l,mid);
    solve(mid,r);
}
int find_best(int n) {
    solve(0,n-1);
    assert(ans!=-1);
    return ans;
}

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