oj.uz

Submission #66272

# Submission time Handle Problem Language Result Execution time Memory
66272 2018-08-10T07:14:14 Z FedericoS The Big Prize (IOI17_prize) C++14
0 / 100
 131 ms 22576 KB 
#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==10000)
            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.0

# Verdict Execution time Memory Grader output
1 Runtime error 103 ms 22468 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Runtime error 131 ms 22576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -