제출 #74138

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
74138		Vahan	커다란 상품 (IOI17_prize)	C++17	97.63 / 100	50 ms	7024 KiB

prize

#include "prize.h"
#include<vector>
using namespace std;
vector<int> res[200005];
int t=-1,u[200005],gum[200005];
vector<int> askk(int a)
{
    vector<int> v;
    v=ask(a);
    gum[a]=v[0]+v[1];
    u[a]=1;
    return v;
}
void bin(int l,int r)
{
    if(t!=-1)
        return;
    int mid=(l+r)/2;
    if(mid==l)
        return;
    res[mid]=askk(mid);
    if(gum[mid]==0)
    {
        t=mid;
        return;
    }
    int x=0,y=0;
    int mec_qan=0;
    if(gum[mid]==gum[l])
    {
        for(int i=l+1;i<mid;i++)
        {
            if(u[i]==1 && gum[i]<gum[l])
                mec_qan++;
        }
    }
    if(res[mid][0]-res[l][0]==mec_qan)
        x=1;
    if(res[mid][0]==res[l][0] && res[mid][1]==res[l][1])
        x=1;
    if(x==0)
        bin(l,mid);
    if(t!=-1)
        return;
    if(res[mid][0]==res[r][0] && res[mid][1]==res[r][1])
        y=1;
    mec_qan=0;
    if(gum[mid]==gum[r])
    {
        for(int i=mid+1;i<r;i++)
        {
            if(u[i]==1 && gum[i]<gum[r])
                mec_qan++;
        }
    }
    if(res[r][0]-res[mid][0]==mec_qan)
        y=1;
    if(y==0)
        bin(mid,r);
}
int find_best(int n) {
	res[0]=askk(0);
	res[n-1]=askk(n-1);
	if(gum[0]==0)
        t=0;
    if(gum[n-1]==0)
        t=n-1;
    bin(0,n-1);
	return t;
}

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