Submission #406989

#	Time	Username	Problem	Language	Result	Execution time	Memory
406989		Peti	The Big Prize (IOI17_prize)	C++14	20 / 100	91 ms	336 KiB

prize

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

using namespace std;

const int bont = 511;
int ert = 0;
mt19937 rng2(chrono::steady_clock::now().time_since_epoch().count());

int megold(int l, int r, vector<int> ansl, vector<int> ansr){
    if(l+1 >= r) return -1;
    int m1 = (l+r)/2;
    int m2 = m1;
    vector<int> ans = ask(m1);
    if(ans[0] + ans[1] == 0) return m1;
    vector<int> ans2 = ans;
    while(m1-1 > l && ans[0]+ans[1] != ert){
        m1--;
        ans = ask(m1);
        if(ans[0] + ans[1] == 0) return m1;
    }
    while(m2+1 < r && ans2[0]+ans2[1] != ert){
        m2++;
        ans2 = ask(m2);
        if(ans2[0] + ans2[1] == 0) return m2;
    }
    return max((ansl[0] < ans[0] ? megold(l, m1, ansl, ans) : -1), (ans2[0] < ansr[0] ? megold(m2, r, ans2, ansr) : -1));
}


int find_best(int n) {
    int s = 0;
    vector<int> ans = {0, 0};
    for(int i = 0; i < 20; i++){
        int x = rng2()%n;
        vector<int> ans2 = ask(x);
        if(ans2[0] + ans2[1] == 0) return x;
        if(ans2[0] + ans2[1] > ans[0] + ans[1])
            ans = ans2;
    }
    ert = ans[0] + ans[1];

    ans = ask(s);
    while(s < n){
        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;
        }

        if(ans[0] < ans2[0]){
            int temp = megold(s, e, ans, ans2);
            if(temp != -1)
                return temp;
        }

        s = s2;
        if(e == s-1){
            ans = ans2;
            s--;
        } else
            ans = ask(s);
    }
	return -1;
}

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