제출 #1028677

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

prize

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

using namespace std;

int cnt;
int L, R;

int solve (int l, int r, int cl, int cr) {
	if (l > r || cl + cr == cnt || l > R || r < L)
		return 0;
	if (l == r) {
		vector<int> a = ask(l);
		if (a[0] + a[1] == 0)
			return l;
		if (a[0] + a[1] != cnt) {
			if (a[0] == 0)
				L = max (L, l + 1);
			if (a[1] == 0)
				R = min (R, l - 1);
		}
		return 0;
	}
	int wef = cl + cr;
	int mid = (l + r) >> 1;
	int mn = mid, mx = mid;
	for (int i = 0; i < cnt - wef; i++) {
		int x;
		if (i % 2 == 1) {
			x = mid + i / 2 + 1;
		} else {
			x = mid - i / 2;
		}
		mn = min (mn, x);
		mx = max (mx, x);
		vector<int> a = ask(x);
		if (a[0] + a[1] == 0)
			return x;
		if (a[0] + a[1] == cnt) {
			int ans = 0;
				if (x == mn) 
					ans ^= solve (l, mn - 1, cl, a[1]);
				else
					ans ^= solve (l, mn - 1, cl, a[1] + i);
				if (x == mx)
					ans ^= solve (mx + 1, r, a[0], cr);
				else
					ans ^= solve (mx + 1, r, a[0] + i, cr);
			return ans;
		}
		if (a[0] == 0)
			L = max (L, x + 1);
		if (a[1] == 0)
			R = min (R, x - 1);
	}
	return 0;
}

int find_best(int n) {
	R = n - 1;
	L = 0;
	for (int i = max (0, n - 400); i < n; i++) {
		vector<int> a = ask(i);
		if(a[0] + a[1] == 0)
			return i;
		cnt = max (cnt, a[0] + a[1]);
	}
	return solve (0, n - 1, 0, 0);
}

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