Submission #1165061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165061		irmuun	The Big Prize (IOI17_prize)	C++20	20 / 100	26 ms	2864 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const int maxn=2e5+5;

vector<int>pos,f;

int N,mx=0,q=0;
int L[maxn],R[maxn];

void solve(int l,int r,bool have){
    if(r<l) return;
    if(have==false){
        vector<int>res=ask(r);
        L[r]=res[0];
        R[r]=res[1];
        if(res[0]+res[1]==mx&&L[pos.back()]==L[r]){
            for(int i=l;i<=r;i++){
                L[i]=L[r];
                R[i]=R[r];
                pos.pb(i);
            }
            return;
        }
    }
    int mid=(l+r)/2;
    vector<int>res=ask(mid);
    L[mid]=res[0];
    R[mid]=res[1];
    if(res[0]+res[1]==mx){//u
        if(L[pos.back()]==L[mid]){//nothing is between them
            for(int i=l;i<=mid;i++){
                L[i]=L[mid];
                R[i]=R[mid];
                pos.pb(i);
            }
            solve(mid+1,r,false);
            return;
        }
        solve(l,mid-1,true);
        pos.pb(mid);
        solve(mid+1,r,true);
    }
    else{
        solve(l,mid-1,true);
        f.pb(mid);
        solve(mid+1,r,true);
    }
    return;
}

int find_best(int n){
    N=n;
    for(int i=0;i<min(447,n);i++){
        vector<int>res=ask(i);
        L[i]=res[0];
        R[i]=res[1];
        if(res[0]+res[1]==0){
            return i;
        }
        mx=max(mx,res[0]+res[1]);
    }
    for(int i=0;i<min(447,n);i++){
        if(L[i]+R[i]==mx){
            pos.pb(i);
        }
        else{
            f.pb(i);
        }
    }
    if(R[pos.back()]>0){
        solve(pos.back()+1,n-1,true);
    }
    for(int i:f){
        if(L[i]+R[i]==0){
            return i;
        }
    }
    return 0;
}

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