Submission #429618

#	Time	Username	Problem	Language	Result	Execution time	Memory
429618		2fat2code	The Big Prize (IOI17_prize)	C++17	90 / 100	163 ms	364 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define fr first
#define sc second
//#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int xmax = 500;

int maxi = 0;

int find_best(int n) {
	for(int i=0;i<min(n, xmax);i++){
        vector<int>arr = ask(i);
        maxi = max(maxi, arr[0] + arr[1]);
	}
	int l = 0, r = n - 1;
	for(int i=1;i<=maxi;i++){
        int ok = 0;
        r = n - 1;
        while(l <= r){
            int mid = l + (r - l) / 2;
            vector<int>rs = ask(mid);
            if((rs[0] + rs[1]) == maxi){
                if(rs[0] >= i){
                    r = mid - 1;
                }
                else{
                    l = mid + 1;
                }
            }
            else{
                if(!(rs[0] + rs[1])){
                    return mid;
                }
                ok = mid;
                r = mid - 1;
            }
        }
        l = ok + 1;
	}
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:51:1: warning: control reaches end of non-void function [-Wreturn-type]
   51 | }
      | ^

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