Submission #1269594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269594		AlgorithmWarrior	The Big Prize (IOI17_prize)	C++20	100 / 100	15 ms	4736 KiB

prize

#include "prize.h"

#include <bits/stdc++.h>

using namespace std;

int const NMAX=200005;
vector<int>rasp[NMAX];
int maxim;
#define pii pair<int,int>
#define ff first
#define ss second
int raspuns_final;

void intrb(int i){
    vector<int>v=ask(i-1);
    rasp[i]=v;
    if(v[0]+v[1]==0)
        raspuns_final=i-1;
}

pii extinde(int pos){
    if(rasp[pos][0]+rasp[pos][1]==maxim)
        return {pos,pos};
    int l=pos;
    while(rasp[l-1].empty()){
        --l;
        intrb(l);
        if(rasp[l][0]+rasp[l][1]==maxim)
            break;
    }
    int r=pos;
    while(rasp[r+1].empty()){
        ++r;
        intrb(r);
        if(rasp[r][0]+rasp[r][1]==maxim)
            break;
    }
    return {l,r};
}

void cauta(int l,int r){
    int mij=(l+r)/2;
    intrb(mij);
    pii per=extinde(mij);
    if(l<per.ff && rasp[l-1]!=rasp[per.ff])
        cauta(l,per.ff-1);
    if(per.ss<r && rasp[per.ss]!=rasp[r+1])
        cauta(per.ss+1,r);
}

int find_best(int n){
    int pas=sqrt(n);
    int i;
    for(i=pas;i<=n;i+=pas){
        intrb(i);
        maxim=max(maxim,rasp[i][0]+rasp[i][1]);
    }
    rasp[0]={0,maxim};
    rasp[n+1]={maxim,0};
    for(i=pas;i<=n;i+=pas)
        extinde(i);
    int ult=0;
    for(i=1;i<=n+1;++i)
        if(!rasp[i].empty() && rasp[i][0]+rasp[i][1]==maxim){
            if(rasp[ult+1].empty())
                cauta(ult+1,i-1);
            ult=i;
        }
    return raspuns_final;
}

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