Submission #138570

#	Time	Username	Problem	Language	Result	Execution time	Memory
138570		rajarshi_basu	The Big Prize (IOI17_prize)	C++14	97.38 / 100	59 ms	540 KiB

prize

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <functional>
 
#include "prize.h"

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i = a;i<=b;i++)
#define ll long long int
#define pb push_back
#define vi vector<int>
#define ff first
#define ss second
#define vv vector
#define ii pair<int,int>
 
using namespace std;
 
const int MAXN = 2e5 + 1;
const ll INF = 1e17;

bool sp[MAXN];
int ans = -1;
int brute(int n){
    FOR(i,n){
        vi a = ask(i);
        if(a[0] == 0 and a[1] == 0)return i;
    }
}
int mx = 0;
void binsrch(int l,int r,int sp_left,int sp_right){
    if(l > r)return;
    if(ans != -1)return;
    if(sp_right + sp_left == mx)return;
    int mid = (l+r)/2;
    vi a = ask(mid);
    if(a[0] + a[1] == mx){
        // this is a lollipop;
        binsrch(l,mid-1,sp_left,a[1]);
        binsrch(mid+1,r,a[0],sp_right);
    }else{
        // now we extend the pointers to both directions to find the closest lollipops
        if(a[0] + a[1] == 0){
            ans = mid;
            return;
        }
        int rptr = mid+1;
        vi a1;
        while(rptr <= r){
            a1 = ask(rptr);
            if(a1[0] + a1[1] == 0){
                ans = rptr;
                return;
            }else if(a1[0] + a1[1] == mx){
                binsrch(rptr+1,r,a1[0],sp_right);
                //binsrch(l,mid-1,sp_left,a1[1] + )
                break;
            }else{
                rptr++;
            }
        }
        if(ans != -1)return;
        int lptr = mid-1;
        while(lptr >= l){
            a1 = ask(lptr);
            if(a1[0] + a1[1] == 0){
                ans = lptr;
                return;
            }else if(a1[0] + a1[1] == mx){
                binsrch(l,lptr-1,sp_left,a1[1]);
                break;
            }else{
                lptr--;
            }
        }
    }
}

int find_best(int n){
    if(n <= 5000)return brute(n);
    FOR(i,500){
        vi a = ask(i);

        mx = max(a[0]+a[1],mx);
    }
    binsrch(0,n-1,0,0);
    return ans;
}

Compilation message (stderr)

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

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