제출 #1164532

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164532		irmuun	The Big Prize (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;
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(1+res[0]+res[1]>=N/2){//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;
    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);
    }
    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