Submission #828215

#	Time	Username	Problem	Language	Result	Execution time	Memory
828215		tolbi	The Big Prize (IOI17_prize)	C++17	20 / 100	59 ms	1356 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];
}
int eb = -1;
void solve(int l, int r){
    if (l==r){
        if (querys(l)==0) ans=l;
        return;
    }
    if (querys(l)!=eb){
        if (querys(l)==0){
            ans=l;
            return;
        }
        solve(l+1,r);
        return;
    }
    if (querys(r)!=eb){
        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);
    return;
}
int find_best(int n) {
    for (int i = 0; i < 23; i++){
        int pos = ayahya()%n;
        eb=max(eb,querys(pos));
    }
    solve(0,n-1);
    return ans;
}

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