Submission #66286

#	Time	Username	Problem	Language	Result	Execution time	Memory
66286		FedericoS	The Big Prize (IOI17_prize)	C++14	100 / 100	101 ms	11580 KiB

prize

#include "prize.h"
#include <assert.h>
#include <iostream>
#include <cmath>
using namespace std;

int N,S,K;
vector<int> A;
vector<int> M[200005];
int calls;
vector<int> vuoto(2,-1);

vector<int> q(int k){

    if(k==-1){
        vector<int> r(2,0);
        r[1]=S;
        return r;
    }

    if(M[k]==vuoto){
        calls++;
        if(calls==10000)
            assert(false);
        M[k]=ask(k);
    }

    //cout<<"q("<<k<<")="<<M[k][0]<<","<<M[k][1]<<endl;
    return M[k];
}

int sinistra(int k){

    int y=k;
    vector<int> V;
    int res=0;
    V=q(k);

    while(V[0]+V[1]!=S){
        res++;
        V=q(--k);
    }

    //cout<<"sinistra("<<y<<")="<<res+V[0]<<endl;
    return res+V[0];

}

int find_best(int n) {

    N=n;
    fill(M,M+N,vuoto);

    for(int i=0;i<min(N,500);i++){
        A=q(i);
        S=max(S,A[0]+A[1]);
        if(S>(int)sqrt(N))
            break;
    }

    while(K<S){

        int l=0,r=N,m;

        while(l<r){
            m=(l+r)/2;
            if(sinistra(m)<=K)
                l=m+1;
            else
                r=m;
        }

        K++;
        A=q(l);
        if(A[0]==0 and A[1]==0)
            return l;

    }

}

Compilation message (stderr)

prize.cpp: In function 'int sinistra(int)':
prize.cpp:34:9: warning: unused variable 'y' [-Wunused-variable]
     int y=k;
         ^
prize.cpp: In function 'int find_best(int)':
prize.cpp:80:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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