Submission #406939

#	Time	Username	Problem	Language	Result	Execution time	Memory
406939		Peti	The Big Prize (IOI17_prize)	C++14	90 / 100	86 ms	328 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"

using namespace std;

const int bont = 1600;

int find_best(int n) {
    int s = 512, ert = 0;

    for(int i = 0; i < min(n, 512); i++){
        vector<int> ans = ask(i);
        if(ans[0]+ans[1] == 0) return i;
        ert = max(ert, ans[0]+ans[1]);
    }

    while(s < n){
        vector<int> ans = ask(s);
        if(ans[0]+ans[1] == 0)
            return s;
        while(ans[0]+ans[1] != ert){
            s++;
            ans = ask(s);
            if(ans[0]+ans[1] == 0)
                return s;
        }

        int e = min(s+bont, n-1);
        int s2 = e+1;
        vector<int> ans2 = ask(e);
        if(ans2[0]+ans2[1] == 0)
            return e;
        while(s < e && ans2[0]+ans2[1] != ert){
            e--;
            ans2 = ask(e);
            if(ans2[0]+ans2[1] == 0)
                return e;
        }

        while(s+1 < e && ans[0] < ans2[0]){
            int l = s, r = e;
            while(l+1 < r){
                int m = (l+r)/2;
                vector<int> ans3 = ask(m);

                if(ans3[0]+ans3[1] == 0) return m;

                if(ans3[0]+ans3[1] != ert || ans3[0] != ans[0])
                    r = m;
                else
                    l = m;
            }
            s = l+1;
            ans = ask(s);
            if(ans[0]+ans[1] == 0) return s;
            while(s < e && ans[0]+ans[1] != ert){
                s++;
                ans = ask(s);
                if(ans[0]+ans[1] == 0)
                    return s;
            }
        }

        s = s2;
    }
	return -1;
}

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