Submission #585340

#	Time	Username	Problem	Language	Result	Execution time	Memory
585340		Vanilla	The Big Prize (IOI17_prize)	C++17	90 / 100	111 ms	11344 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
int nr[] = {1, 2, 5, 26, 677};
const int maxn = 2e5 + 2;
vector <vector <int> > mp (maxn, vector <int> {-1, -1});

vector <int> get (int x) {
	return mp[x] = ((mp[x] == vector <int> {-1, -1}) ? ask(x) : mp[x]);
}
 
int solve (int l, int r) {
	if (l > r) return -1;
	if (l == r) {
		vector <int> q = get(l);
		if (q[0] + q[1] == 0) return l;
		return -1;
	}
	vector <int> ql = get(l);
	vector <int> qr = get(r);
	if (ql[0] + ql[1] == 0) return l;
	if (qr[0] + qr[1] == 0) return r;
	if (ql[0] + ql[1] == qr[0] + qr[1] && qr[0] - ql[0] == 0) return -1;
	int mid = (l + r) / 2;
	int rs = solve(l, mid);
	return (rs == -1 ? solve(mid + 1, r): rs);
 
}
 
int find_best(int n) {
	return solve(0, n - 1);
}

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