Submission #138554

#	Time	Username	Problem	Language	Result	Execution time	Memory
138554		rajarshi_basu	The Big Prize (IOI17_prize)	C++14	Compilation error	0 ms	0 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;
/*
struct DSU{
    int parent[MAXN];
    void init(){
        FOR(i,MAXN)parent[i] =i;
    }
    int find(a){
        if(a != parent[a])parent[a] = find(parent[a]);
        return parent[a];
    }
    void merge(int a,int b){
        if(!isSame(a,b)){
            int pa = find(a);
            int pb = find(b);
            parent[pa] = pb;
        }
    }
    bool isSame(int a,int b){
        return find(a) == find(b);
    }
} dsu;*/

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(sp[0] + sp[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] + a[1] == mx){
                binsrch(rptr+1,r,a[0],sp_right);
                break;
            }else{
                rptr++;
            }
        }
        int lptr = mid-1;
        while(lptr >= l){
            a1 = ask(lptr);
            if(a1[0] + a[1] == 0){
                ans = lptr;
                return;
            }else if(a[0] + a[1] == mx){
                binsrch(l,lptr-1,sp_left,a[1]);
                break;
            }else{
                lptr--;
            }
        }
    }
}

int find_best(int n){
    if(n <= 5000)return brute(n);
    FOR(i,500){
        int* 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 find_best(int)':
prize.cpp:104:23: error: cannot convert 'std::vector<int>' to 'int*' in initialization
         int* a = ask(i);
                       ^
prize.cpp: In function 'int brute(int)':
prize.cpp:53:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^