제출 #827011

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

prize

#include<bits/stdc++.h>
#include "prize.h"

using namespace std;

bool findans=0;
int pos=0;
int maxsum=0;

void solve(int le, int ri, int bal_le, int bal_ri, int br)
{
    ///cout<<le<<" "<<ri<<endl;
    if(le>ri || !br) return;
    int mid=(le+ri)/2;
    vector<int> res=ask(mid);
    ///cout<<mid<<endl;
    if(res[0] + res[1] == 0)
    {
        findans=1;
        pos=mid;
        return;
    }
    if(res[0]+res[1]==maxsum)
    {
        solve(le, mid-1, bal_le, res[1], res[0]-bal_le);
        solve(mid+1, ri, res[0], bal_ri, res[1]-bal_ri);
        return;
    }
    int m2=mid;
    while(m2-1>=le && res[0]+res[1]!=maxsum)
    {
        m2--;
        res=ask(m2);
        cout<<m2<<endl;
        if(res[0] + res[1] == 0)
        {
            findans=1;
            pos=m2;
            return;
        }
    }
    if(m2==le && res[0]+res[1]<maxsum) solve(mid+1, ri, bal_le+mid-le+1, bal_ri, br-mid+le-1);
    else
    {
        solve(le, m2, bal_le, res[1], res[0]-bal_le);
        solve(mid+1, ri, maxsum-bal_ri-(br-(res[0]-bal_le)-(mid-m2)), bal_ri, br-(res[0]-bal_le)-(mid-m2));

    }
}

int find_best(int n)
{
	for(int i = 0; i < 500 && i<n; i++)
    {
		vector<int> res = ask(i);
		if(res[0] + res[1] == 0) return i;
        if(res[0]+res[1]>maxsum) maxsum=res[0]+res[1];
	}
    solve(0, n-1, 0, 0, maxsum);
	return pos;
}

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