제출 #1317564

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

prize

#include <bits/stdc++.h>
#include "prize.h"
using namespace std;

int smax = 0;
int ans = -1;

void getans(int l, int r, int lval, int rval) {
	if (ans != -1) return;
	if (l > r) return;
	
	int mid = (l+r)/2;
	vector <int> res = ask(mid);
	int sum = res[0] + res[1];

	if (sum == 0) {
		ans = mid;
		return;
	}
	if (sum < smax) {
		int lmid = mid-1;
		res = ask(lmid);
		while (res[0] + res[1] < smax && lmid >= l) {
			if (res[0] + res[1] == 0) {
				ans = lmid;
				return;
			}
			lmid--;
			res = ask(lmid);
		}
		getans(l,lmid,lval,res[1]);
		int rmid = mid+1;
		res = ask(rmid);
		while (res[0] + res[1] < smax && rmid <= r) {
			if (res[0] + res[1] == 0) {
				ans = rmid;
				return;
			}
			rmid++;
			res = ask(rmid);
		}
		getans(rmid,r,res[0],rval);
	} else {
		if (res[0] > lval) {
			getans(l,mid-1,lval,res[1]);
		}
		if (res[1] > rval) {
			getans(mid+1,r,res[0],rval);
		}
	}
}

int find_best(int n) {
	vector <int> res;
	for(int i = 0; i < min(n,475); i++) {
		res = ask(i);
		smax = max(smax,res[0] + res[1]);
	}
	getans(0,n-1,0,0);
	return ans;
}

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