Submission #986038

#	Time	Username	Problem	Language	Result	Execution time	Memory
986038		AlphaMale06	The Big Prize (IOI17_prize)	C++14	20 / 100	54 ms	600 KiB

prize

#include <bits/stdc++.h>

#include "prize.h"

using namespace std;

//vector<int> ask(int i);

int find_best(int n){
	if(n<=5000){
        for(int i=0; i<n; i++){
            vector<int> ans = ask(i);
            if(ans[0]==0 && ans[1]==0)return i;
        }
	}
    int summ = 0;
    for(int i=0; i<8; i++){
        int ind = rand()%n;
        vector<int> ans = ask(ind);
        summ=max(summ, ans[0]+ans[1]);
        if(ans[0]==0 && ans[1]==0)return ind;
    }
    int prev=-1;
    for(int i=0; i<summ; i++){
        int l = prev+1, r = n-1;
        int best = n-1;
        while(l<=r){
            int s = l+r>>1;
            vector<int> ans = ask(s);
            if(ans[0]+ans[1]==0)return s;
            if(ans[0]+ans[1]==summ){
                if(ans[0]>i){
                    best=s-1;
                    r=s-1;
                }
                else l=s+1;
            }
            else{
                best = s;
                r=s-1;
            }
        }
        vector<int> ans = ask(best);
        if(ans[0]+ans[1]==0)return best;
    }
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:28:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |             int s = l+r>>1;
      |                     ~^~
prize.cpp:46:1: warning: control reaches end of non-void function [-Wreturn-type]
   46 | }
      | ^

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