제출 #858896

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
858896		abcvuitunggio	커다란 상품 (IOI17_prize)	C++17	97.70 / 100	33 ms	7096 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> a[200000];
int ch[200000];
void query(int i){
    if (a[i].empty())
        a[i]=ask(i);
}
int find_best(int n){
    if (n<=5000)
        for (int i=0;i<n;i++){
            query(i);
            if (!a[i][0]&&!a[i][1])
                return i;
        }
    int mx=0;
    for (int i=0;i<472;i++){
        query(i);
        if (!a[i][0]&&!a[i][1])
            return i;
        mx=max(mx,a[i][0]+a[i][1]);
    }
    int cur=0,cnt=0;
    priority_queue <int, vector <int>, greater <int>> q;
    while (true){
        while (!q.empty()){
            if (a[q.top()][0]==cnt){
                cur=q.top()+1;
              	q.pop();
            }
            else
                break;
        }
        int l=cur,r=(q.empty()?n-1:q.top()-1);
        if (!q.empty()){
            if (r-l+1==a[q.top()][0]-cnt){
                for (int i=l;i<=r;i++){
                    query(i);
                    if (!a[i][0]&&!a[i][1])
                        return i;
                }
                cnt+=r-l+1;
                cur=q.top()+1;
                while (!a[cur].empty()&&a[cur][0]+a[cur][1]==mx)
                    cur++;
                continue;
            }
        }
        while (l<=r){
            int mid=(l+r)>>1;
            query(mid);
            if (!a[mid][0]&&!a[mid][1])
                return mid;
            if (a[mid][0]+a[mid][1]==mx){
                if (a[mid][0]>cnt){
                    if (!ch[mid])
                        q.push(mid);
                    ch[mid]=1;
                    cur=mid;
                    r=mid-1;
                }
                else
                    l=mid+1;
                continue;
            }
            cur=mid;
            r=mid-1;
        }
        cnt++;
        cur++;
        while (!a[cur].empty()&&a[cur][0]+a[cur][1]==mx)
            cur++;
    }
}

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