제출 #1238151

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1238151		vivkostov	커다란 상품 (IOI17_prize)	C++20	20 / 100	20 ms	412 KiB

prize

//#pragma once
//#include "grader.cpp"
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 mt(time(nullptr));
int sum,lamp,n;
vector<int>a;
void prec()
{
   for(int i=1;i<=5;i++)
   {
       a=(ask(mt()%n));
       sum=max(sum,a[0]+a[1]);
   }
}
void rec(int l,int r,int br,int exl,int exr)
{
    if(lamp||!br||l>r)return;
    int mid=(l+r)/2,ad=1;
    while(true)
    {
        a=ask(mid);
        if(a[0]+a[1]==0)
        {
            lamp=mid+1;
            return;
        }
        if(a[0]+a[1]==sum)break;
        mid+=ad;
        if(mid>r)
        {
            mid=(l+r)/2-1;
            ad=-1;
        }
        if(mid<l)return;
    }
    int dist=abs(mid-(l+r)/2);
    if(mid>=(l+r)/2)
    {
        rec(l,(l+r)/2-1,a[0]-exl-dist,exl,a[1]+dist);
        rec(mid+1,r,a[1]-exr,a[0],exr);
    }
    else
    {
        rec(l,mid-1,a[0]-exl,exl,a[1]);
    }
}
int find_best(int N)
{
    n=N;
    prec();
    rec(0,n-1,sum,0,0);
	return lamp-1;
}

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