Submission #1161336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161336		danglayloi1	The Big Prize (IOI17_prize)	C++20	100 / 100	11 ms	408 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=2e5+5;
int base;
// vector<int> ask(int i)
// {

// }
int solve(int l, int r, int cnt, int le, int ri)
{
    if(l>r || !cnt) return -1;
    int mid=(l+r)>>1;
    vector<int> tmp=ask(mid);
    if(tmp[0]+tmp[1]==0) return mid;
    if(tmp[0]+tmp[1]==base) return max(solve(l, mid-1, cnt-(tmp[1]-ri), le, tmp[1]), solve(mid+1, r, cnt-(tmp[0]-le), tmp[0], ri));
    vector<int> L={0, 0}, R={0, 0};
    int pl=mid-1, pr=mid+1;
    while(pl>=l)
    {
        L=ask(pl);
        if(L[0]+L[1]==0) return pl;
        if(L[0]+L[1]==base) break;
        pl--;
    }
    while(pr<=r)
    {
        R=ask(pr);
        if(R[0]+R[1]==0) return pr;
        if(R[0]+R[1]==base) break;
        pr++;
    }
    return max(solve(l, pl-1, cnt-(L[1]-ri), le, L[1]), solve(pr+1, r, cnt-(R[0]-le), R[0], ri));
}
int find_best(int n)
{
    base=0;
    for(int i = 0; i < min(500, n); i++)
    {
        vector<int> tmp=ask(i);
        base=max(base, tmp[0]+tmp[1]);
        if(base>=100) break;
    }
    return solve(0, n-1, base, 0, 0);
}

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