Submission #33562

#	Time	Username	Problem	Language	Result	Execution time	Memory
33562		top34051	The Big Prize (IOI17_prize)	C++14	90 / 100	66 ms	3772 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 200005;

int N, vmx;
bool vis[maxn];
pii ret[maxn];

pii talk(int pos) {
    pos = min(pos,N-1);
    if(!vis[pos]) {
        vis[pos] = 1;
        auto v = ask(pos);
        ret[pos] = {v[0],v[1]};
    }
    return ret[pos];
}

void solve(int l,int r) {
    if(l>r) return ;
    pii L, R;
    while(l<=r) {
        L = talk(l);
        if(L.X+L.Y==vmx) break;
        l++;
    }
    while(l<=r) {
        R = talk(r);
        if(R.X+R.Y==vmx) break;
        r--;
    }
    int mid = (l+r)/2;
    if(R.X-L.X>0) {
        solve(l,mid);
        solve(mid+1,r);
    }
}

int find_best(int n) {
    int i;
    pii res;
    N = n;
    //vmx
    for(i=0;i<min(N,730);i++) {
        res = talk(i);
        vmx = max(vmx,res.X+res.Y);
    }
//    printf("vmx = %d\n",vmx);
    //get all 1,2,...,v-1
    solve(0,N-1);
    for(i=0;i<N;i++) {
        if(vis[i] && ret[i].X+ret[i].Y!=vmx) {
//            printf("%d : {%d, %d}\n",i,ret[i].X,ret[i].Y);
            if(ret[i].X+ret[i].Y==0) return i;
        }
    }
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:62:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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