Submission #112248

#	Time	Username	Problem	Language	Result	Execution time	Memory
112248		someone_aa	The Big Prize (IOI17_prize)	C++17	90 / 100	96 ms	2236 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#define P pair<int,int>
using namespace std;
const int maxn = 200100;
const int b = 500;
bool visited[maxn];
int q[maxn][2];
int max_sum, ind;
P query(int i) {
    if(visited[i]) return {q[i][0], q[i][1]};
    visited[i] = true;
    vector<int>curr = ask(i);
    q[i][0] = curr[0];
    q[i][1] = curr[1];
    return {q[i][0], q[i][1]};
}

int sum(int i) {
    query(i);
    return q[i][0] + q[i][1];
}

void solve(int l, int r) {
    //cout<<l<<" "<<r<<"\n";
    if(l > r || ind != -1) return;

    P ql = query(l);
    P qr = query(r);

    if(ql.first + ql.second == 0) {
        ind = l;
        return;
    }

    if(qr.first + qr.second == 0) {
        ind = r;
        return;
    }

    if(ql.first + ql.second != max_sum) {
        solve(l+1, r);
        return;
    }

    if(qr.first + qr.second != max_sum) {
        solve(l, r-1);
        return;
    }

    int between  = qr.first - ql.first;
    if(between == 0) return;

    int mid = (l + r) / 2;

    solve(l, mid);
    solve(mid+1, r);
}

int find_best(int n) {
    ind = -1;
    for(int i=0;i<min(n, 500);i++) {
        if(sum(i) == 0) return i;
        max_sum = max(max_sum, sum(i));
    } //max_sum = 1;

    for(int l=0;l<n;l+=b) {
        int r = min(n-1, l+b-1);
        solve(l, r);
    }
    return ind;
}

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