Submission #1164536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164536		irmuun	커다란 상품 (IOI17_prize)	C++20	0 / 100	2 ms	1988 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()

void solve(int l,int r,int &n,vector<int>&L,vector<int>&R,int &mx,vector<int>&pos,vector<int>&f){
    if(r<l) 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,n,L,R,mx,pos,f);
            return;
        }
        solve(l,mid-1,n,L,R,mx,pos,f);
        pos.pb(mid);
        solve(mid+1,r,n,L,R,mx,pos,f);
    }
    else{
        solve(l,mid-1,n,L,R,mx,pos,f);
        f.pb(mid);
        solve(mid+1,r,n,L,R,mx,pos,f);
    }
    return;
}

int find_best(int n){
    vector<int>L(n),R(n),pos,f;
    int mx=0;
    for(int i=0;i<min(500,n);i++){
        vector<int>res=ask(i);
        L[i]=res[0];
        R[i]=res[0];
        if(res[0]+res[1]==0){
            return i;
        }
        mx=max(mx,res[0]+res[1]);
    }
    for(int i=0;i<min(500,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,n,L,R,mx,pos,f);
    }
    for(int i:f){
        vector<int>res=ask(i);
        if(res[0]+res[1]==0){
            return i;
        }
    }
    return 0;
}
// 1 2 5 26 677

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