Submission #348340

#	Time	Username	Problem	Language	Result	Execution time	Memory
348340		Hideo	The Big Prize (IOI17_prize)	C++17	20 / 100	86 ms	11372 KiB

prize

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

using namespace std;

#define ll long long
#define mk make_pair

const int N = 2e5 + 7;

vector < int > a[N];
int mx, ans = -1;
int cnt;
int period = 800;

void divide (int l, int r){
    if (a[l][0] == -1)
        a[l] = ask(l);
    if (a[l][0] + a[l][1] == 0){
        ans = l;
        return;
    }
    if (a[r][0] == -1)
        a[r] = ask(r);
    if (a[r][0] + a[r][1] == 0){
        ans = r;
        return;
    }
    if (l + 1 >= r)
        return;
    if (a[l][0] + a[l][1] < mx){
        divide(l + 1, r);
        return;
    }
    if (a[r][0] + a[r][1] < mx){
        divide(l, r - 1);
        return;
    }
    int mid = (l + r) >> 1;
    if (a[mid][0] == -1)
        a[mid] = ask(mid);
    if (a[mid][0] + a[mid][1] == 0){
        ans = mid;
        return;
    }
    if (a[mid][0] + a[mid][1] < mx){
        divide(l, mid - 1);
        divide(mid + 1, r);
        return;
    }
    if (a[mid][1] - a[r][1])
        divide(mid, r);
    if (ans != -1)
        return;
    if (a[l][1] - a[mid][1])
        divide(l, mid);
}

void calc (int l, int r){
    if (a[l][0] + a[l][1] == 0){
        ans = l;
        return;
    }
    while (l < r && a[l][0] + a[l][1] < mx){
        l++;
        if (a[l][0] == -1)
            a[l] = ask(l);
        if (a[l][0] + a[l][1] == 0){
            ans = l;
            return;
        }
    }
    if (a[r][0] + a[r][1] == 0){
        ans = r;
        return;
    }
    while (l < r && a[r][0] + a[r][1] < mx){
        r--;
        if (a[r][0] == -1)
            a[r] = ask(r);
        if (a[r][0] + a[r][1] == 0){
            ans = r;
            return;
        }
    }
    if (l == r)
        return;
    if (a[l][1] - a[r][1])
        divide(l, r);
}

int find_best (int n){
    for (int i = 0; i < n; i++)
        a[i].resize(2);
    for (int i = 0; i < n; i++)
        a[i][0] = a[i][1] = -1;
    for (int i = 0; i < n; i += period){
        a[i] = ask(i);
        mx = max(mx, a[i][0] + a[i][1]);
        if (a[i][0] + a[i][1] == 0)
            return i;
    }
    a[n - 1] = ask(n - 1);
    mx = max(mx, a[n - 1][0] + a[n - 1][1]);
    if (a[n - 1][0] + a[n - 1][1] == 0)
        return n - 1;
    for (int i = 0; i < n; i += period){
        calc(i, min(n - 1, i + period));
        if (ans != -1)
            break;
    }
    //cout << ans << endl;
	return ans;
}

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