Submission #577464

#	Time	Username	Problem	Language	Result	Execution time	Memory
577464		definitelynotmee	The Big Prize (IOI17_prize)	C++98	0 / 100	103 ms	208 KiB

prize

#include<bits/stdc++.h>
#include "prize.h"
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;

int find_best(int n) {
	
    int ct = 0;

    for(int i = 0; i < min(500, n); i++){
        vector<int> ret = ask(i);
        int resp = ret[0]+ret[1];
        ct = max(ct,resp);
    }
    vector<int> cand;

    auto solve =[&](int l, int r, int discl, int discr, auto solve)->void{
        if(r < l)
            return;
        int m = (l+r)>>1;
        int mid = m;
        vector<int> ret = ask(m);
        while(m <= r && ret[0]+ret[1] < ct){
            cand.push_back(m);
            m++;
            if(m <= r)
                ret = ask(m);
        }
        
        if(m > r){
            int m = mid-1;
            if(m < l)
                return;
            ret = ask(m);
            while(m >= l && ret[0]+ret[1] < ct){
                cand.push_back(m);
                m--;
                if(m >= l)
                    ret = ask(m);
            }
            solve(l,m-1,discl,ret[1],solve);
            return;
        }
        solve(l,mid-1,discl,ret[1]+m-mid,solve);
        solve(m+1,r,ret[0],discr,solve);
    };
    solve(0,n-1,0,0,solve);
    for(int i : cand){
        vector<int> ret = ask(i);
        if(ret[0]+ret[1] == 0){
            return i;
        }
    }

}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:22:17: warning: control reaches end of non-void function [-Wreturn-type]
   22 |     vector<int> cand;
      |                 ^~~~

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