제출 #390651

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
390651		aarr	커다란 상품 (IOI17_prize)	C++14	0 / 100	1 ms	320 KiB

prize

#include "prize.h"
 
#include <bits/stdc++.h>
using namespace std;
 
int n;
const int N = 200 * 1000 + 5;
pair <int, int> res[N];
bool mark[N];
 
void ask_save(int k) {
	if (!mark[k]) {
		vector <int> vec = ask(k);
		res[k].first = vec[0];
		res[k].second = vec[1];
	}
	
}
 
int solve(int s, int e) {
	if (e - s <= 2) {
		return n;
	}
	int md = (s + e) / 2;
	ask_save(md);
	if (res[md].first + res[md].second == 0) {
		return md;
	}
	int ans = n;
	if (res[md] != res[s]) {
		ans = solve(s, md + 1);
		if (ans < n) {
			return ans;
		}
	}
	if (res[md] != res[e - 1]) {
		ans = min(ans, solve(md, e));
	}
	return ans;
}
 
int find_best(int n) {
	ask_save(0);
	ask_save(n - 1);
	if (res[0].first + res[0].second == 0) {
		return 0;
	}
	if (res[n - 1].first + res[n - 1].second == 0) {
		return n - 1;
	}
	return solve(0, n);
}

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