Submission #1317586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317586		nikaa123	커다란 상품 (IOI17_prize)	C++20	20 / 100	2 ms	404 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> vmid = ask(mid);
	if (vmid[0] + vmid[1] == 0) {
		ans = mid;
		return;
	}
	if (vmid[0] + vmid[1] == smax) {
		if (vmid[0] > lval) getans(l,mid-1,lval,vmid[1]);
		if (vmid[1] > rval) getans(mid+1,r,vmid[0],rval);
		return;
	}
	int curr = mid+1;
	int curl = mid-1;
	vector <int> resr,resl;
	bool okl = false; 
	bool okr = false;

	while (curr <= r) {
		resr = ask(curr);
		if (resr[0] + resr[1] == 0) {
			ans = curr;
			return;
		}
		if (resr[0] + resr[1] == smax) {
			okr = true;
			break;
		}
		curr++;
	}

	while (curl >= l) {
		resl = ask(curl);
		if (resl[0] + resl[1] == 0) {
			ans = curl;
			return;
		}
		if (resl[0] + resl[1] == smax) {
			okl = true;
			break;
		}
		curl--;
	}

	if (okr) {
		if (resr[1] > rval) getans(curr+1, r, resr[0], rval);
	}
	if (okr) {
		if (resl[0] > lval) getans(l, curl-1, lval, resl[1]);
	}
}

int find_best(int n) {
	vector <int> res;
	for(int i = 0; i < min(n,500); 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