Submission #334997

#	Time	Username	Problem	Language	Result	Execution time	Memory
334997		LucaDantas	커다란 상품 (IOI17_prize)	C++17	92.92 / 100	75 ms	1488 KiB

prize

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

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count() ^ (long long) (make_unique<char>().get()));

template<typename T> T rnd(T v) {
  T k = (T) rng();
  return (T) (((k % v) + v) % v);
}

#define pb push_back
#define sz(a) (int)((a).size())

const vector<int> good = {0, 0};

constexpr int maxn = 2e5+10;

set<int> s;
// map<int,set<int>> s;
int ans[maxn], base;

// int solve(int l, int r) {
// 	if(l > r) return -1;
// 	int m = (l+r) >> 1;
// 	vector<int> get = ask(m);
// 	if(get == good) return m;
// 	ans[m] = get[0];
// 	auto it = s[get[0]+get[1]].insert(m).first;
// 	if(it == s[get[0]+get[1]].begin() || ans[*prev(it)] != ans[m]) {
// 		int ans = solve(l, m-1);
// 		if(ans != -1) return ans;
// 	}
// 	if(it == --s[get[0]+get[1]].end() || ans[*next(it)] != ans[m]) {
// 		int ans = solve(m+1, r);
// 		if(ans != -1) return ans;
// 	}
// 	return -1;
// }

int solve(int l, int r) {
	if(l > r) return -1;
	int m = (l+r) >> 1;
	vector<int> get = ask(m);
	if(get == good) return m;
	ans[m] = get[0];
	auto it = s.begin();
	if(get[0]+get[1] == base)
		it = s.insert(m).first;
	if(get[0]+get[1] != base || it == s.begin() || ans[*prev(it)] != ans[m]) {
		int ans = solve(l, m-1);
		if(ans != -1) return ans;
	}
	if(get[0]+get[1] != base || it == --s.end() || ans[*next(it)] != ans[m]) {
		int ans = solve(m+1, r);
		if(ans != -1) return ans;
	}
	return -1;
}

int find_best(int n) {
	for(int i = 0; i < min(475, n); i++) {
		vector<int> a = ask(i);
		base = max(base, a[0]+a[1]);
	}
	return solve(0, n-1);
}

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