제출 #1067544

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

prize

// Ignut

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

vector<int> ask(int i);

map<int, vector<int>> mp;
vector<int> Ask(int i) {
	// cout << "ask " << i << '\n';
	if (mp.count(i)) return mp[i];
	vector<int> ans = ask(i);
	mp[i] = ans;
	return ans;
}

int SZ = 1000;

int n;

vector<int> GetVec(int pos) {
	vector<int> res;
	for (int i = pos; i >= max(0, pos - SZ / 2); i --) res.push_back(pos);
	for (int i = pos + 1; i <= min(n - 1, pos + SZ / 2); i ++) res.push_back(pos);
	return res;
}

int find_best(int nn) {
	n = nn;
	int cntB = 0;
	for (int i = 0; i < min(n, SZ); i ++) {
		vector<int> vec = Ask(i);
		if (vec[0] + vec[1] == 0) return i;
		cntB = max(cntB, vec[0] + vec[1]);
	}
	int L = -1;
	for (int i = 0; i < cntB; i ++) {
		int lo = L + 1, hi = n - 1;
		while (lo < hi) {
			int mid = lo + (hi - lo) / 2;
			int val = mid;
			for (int v : GetVec(mid)) {
				vector<int> vec = Ask(v);
				if (vec[0] + vec[1] == 0)
					return v;
				if (vec[0] + vec[1] != cntB) continue;
				val = v; break;
			}
			vector<int> vec = Ask(val);
			if (vec[0] > i)
				hi = mid - 1;
			else
				lo = mid + 1;
		}
		vector<int> vec = Ask(lo);
		if (vec[0] + vec[1] == 0) return lo;
		L = lo;
	}
	// while (L < n - 1) {
	// 	while (lo < hi) {
	// 		int mid = lo + (hi - lo) / 2;
	// 	}	
	// }
	return n - 1;
}

/*
8
3 2 3 1 3 3 2 3
*/

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