Submission #66270

#	Time	Username	Problem	Language	Result	Execution time	Memory
66270		FedericoS	The Big Prize (IOI17_prize)	C++14	0 / 100	51 ms	22544 KiB

prize

#include "prize.h"
#include <assert.h>
#include <iostream>
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==1000)
            assert(false);
        M[k]=ask(k);
    }

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

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]);
    }

    while(K<S){

        //cout<<"K="<<K<<endl;
        int l=0,r=N,m;

        while(l<r){

            m=(l+r)/2;
            //cout<<"m= "<<m<<endl;
            A=q(m);

            if(A[0]+A[1]==S){
                if(A[0]<K)
                    l=m+1;
                else
                    r=m;
                //cout<<"caso1 "<<l<<" "<<r<<endl;
            }
            else{
                int p=m;
                while(A[0]+A[1]!=S)
                    A=q(--p);
                if(A[0]<K){
                    K+=m-p;
                    //cout<<"caso2 break "<<l<<" "<<r<<" "<<p<<endl;
                    break;
                }
                else
                    r=m;
                //cout<<"caso2 "<<l<<" "<<r<<" "<<p<<endl;
            }

        }

        q(l+1);
        K++;
        //cout<<endl;

    }

    //cout<<M[i][0]<<" "<<M[i][1]<<endl;
    //cout<<"******\n";

    for(int i=0;i<N;i++)
        if(M[i][0]==0 and M[i][1]==0)
            return i;

    for(int i=1;i<N;i++)
        if(M[i]==vuoto and M[i-1]!=vuoto)
            q(i);

    for(int i=0;i<N;i++)
        if(M[i][0]==0 and M[i][1]==0)
            return i;

    return -1;

}

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