제출 #1165062

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1165062		irmuun	커다란 상품 (IOI17_prize)	C++20	20 / 100	24 ms	2856 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){
    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);
            return;
        }
        solve(l,mid-1);
        pos.pb(mid);
        if(R[pos.back()]>0){
            solve(mid+1,r);
        }
    }
    else{
        vector<int>add;
        add.pb(mid);
        for(int i=mid-1;i>=l;i--){
            vector<int>rs=ask(i);
            L[i]=rs[0];
            R[i]=rs[1];
            if(L[i]+R[i]<mx){
                add.pb(i);
                continue;
            }
            else{
                if(L[i]==L[pos.back()]){
                    for(int j=l;j<=i;j++){
                        L[j]=L[i];
                        R[j]=L[j];
                        pos.pb(j);
                    }
                    return;
                }
                else{
                    solve(l,i-1);
                }
                break;
            }
        }
        reverse(all(add));
        for(int i:add) f.pb(i);
        if(R[pos.back()]>0){
            solve(mid+1,r);
        }
    }
    return;
}

int find_best(int n){
    N=n;
    for(int i=0;i<min(500,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(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);
    }
    for(int i:f){
        if(L[i]+R[i]==0){
            return i;
        }
    }
    return 0;
}

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