Submission #538879

#	Time	Username	Problem	Language	Result	Execution time	Memory
538879		Deepesson	The Big Prize (IOI17_prize)	C++17	100 / 100	48 ms	344 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
typedef std::pair<int,int> pii;
int diamante=-1;
int N;
pii pergunta(int p){
    auto x = ask(p-1);
    if(!(x[0]+x[1])){
        diamante=p;
    }
    return {x[0],x[1]};
}
int range = 480;
int maxa=0;
void cdc(int l=1,int r=N,int left=0,int right=0){
    if(diamante!=-1)return;
    if(l>r)return;
    if(left+right==maxa)return;

    int curl=0,curr=1;
    int m = (l+r)/2;
    int computou=0;
    int size=r-l+1;
    pii ans;
    int lf=m,rf=m;
    int split=m;

    while(computou!=size){
        if(left+right+computou==maxa)return;
        if(curl<curr){
            int novpos = m-curl;
            ++curl;
            if(novpos<l){continue;}
            lf=novpos;
            split=novpos;
            ans = pergunta(novpos);
            if(ans.first+ans.second==maxa)break;
        }else {
            int novpos = m+curr;
            ++curr;
            if(novpos>r){continue;}
            rf=novpos;
            split=novpos;
            ans = pergunta(novpos);
            if(ans.first+ans.second==maxa)break;
        }
        ++computou;
    }

    if(computou+1>=size)return;

    if(split==lf){
        cdc(l,lf-1,left,ans.second);
    }
    else if(split==rf&&lf-1>=l){
       /// assert(cheatask(lf-2)[1]==ans.second+computou);
        cdc(l,lf-1,left,ans.second+computou);
    }else assert(0);///Erro! Eh na direita ou esquerda

    if(split==lf&&r>=rf+1){
      ///  std::cout<<cheatask(rf)[0]<<"!!\n";
       /// std::cout<<computou<<" "<<cheatask(rf)[0]<<" "<<ans.first<<" ("<<lf<<"  "<<rf<<") "<<l<<" "<<r<<" "<<g[split]<<"\n";
     ///   assert(ans.first+computou==cheatask(rf)[0]);
        cdc(rf+1,r,ans.first+computou,right);
    }
    else if(split==rf){
        cdc(rf+1,r,ans.first,right);
    }else assert(0);///Erro! Eh na direita ou esquerda

}

int find_best(int n) {
    N=n;
    range=std::min(range-1,N);
    std::vector<int> vals;
    for(int i=1;i<range;++i){
        pii u = pergunta(i);
        maxa=std::max(u.first+u.second,maxa);
        if(maxa>100){
            range=i+1;
            break;
        }
        vals.push_back(u.first+u.second);
    }
    int count=0;
    for(auto&x:vals)if(x<maxa)++count;
    cdc(range,N,count,0);
    assert(diamante!=-1);
    return diamante-1;
}

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