제출 #1164540

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164540		irmuun	커다란 상품 (IOI17_prize)	C++20	0 / 100	2 ms	436 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;
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);
    //     solve(mid+1,r);
    // }
    // else{
    //     solve(l,mid-1);
    //     f.pb(mid);
    //     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[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);
    }
    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