Submission #334982

#	Time	Username	Problem	Language	Result	Execution time	Memory
334982		LucaDantas	The Big Prize (IOI17_prize)	C++17	20 / 100	123 ms	3060 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;
int base, N;

int solve(vector<int>& v, int l, int r) {
	if(!sz(v)) return -1;
	// assert(l+r != base);
	if(sz(v) == 1) {
		if(ask(v[0]) == good) return v[0];
		return -1;
	}
	// printf("l, r == %d %d, b, e ==  %d %d\n", l, r, v[0], v.back());
	// printf("l, r == %d %d %d %d %d\n", l, r, v[0], v.back(), sz(v));
	// for(int x : v)
	// 	printf("%d ", x);
	// printf("\n");
	int m = sz(v)/2;
	vector<int> a, b;
	for(int i = 0; i < m; i++)
		a.pb(v[i]);
	vector<int> res = ask(v[m]);
	if(res == good) return v[m];
	if(res[0]+res[1] == base) {
		// printf("v %d\n", v[m]);
		for(int i = m; i < sz(v); i++)
			b.pb(v[i]);
		if(res[0] - l) {
			int ans = solve(a, l, res[1]);
			if(ans != -1) return ans;
		}
		if(r - res[1]) {
			int ans = solve(b, res[0], r);
			if(ans != -1) return ans;
		}
	} else {
		int seen = 1, p = v[m]+1;
		bool ok = 0;
		while(p <= v.back()) {
			// printf("p %d\n", p);
			res = ask(p);
			if(res == good) return p;
			if(res[0]+res[1] == base) {
				for(int i = p+1; i <= v.back(); i++)
					b.pb(i);
				if(res[0] - l - seen) {
					int ans = solve(a, l, res[1]+seen);
					if(ans != -1) return ans;
				}
				if(r - res[1]) {
					int ans = solve(b, res[0], r);
					if(ans != -1) return ans;
				}
				ok = 1;
				break;
			}
			++p, ++seen;
		}
		if(!ok) {
			// // assert(0);
			// // Isso vai dar errado mas quero ver até aonde vai
			// // Depois é só fazer o meio andar pra esquerda tbm
			// assert(ask(v.back()+1)[0]+ask(v.back()+1)[1] == base);
			// int r = seen+(v.back()==N-1?0:(ask(v.back()+1)[1]));
			// // if(r + l != base) {
			// 	int ans = solve(a, l, r);
			// 	if(ans != -1) return ans;
			// // }
			a.clear();
			p = v[m]-1;
			while(p >= v[0]) {
				res = ask(p);
				if(res == good) return p;
				if(res[0]+res[1] == base) {
					if(res[0]-l) {
						int ans = solve(a, l, seen+res[1]);
						if(ans != -1) return ans;
					}
					break;
				}
				++seen, --p;
			}
		}
	}
	return -1;
}

map<int,int> cnt;

int find_best(int n) {
	N = n;
	int last = 0;
	if(n < 5000) {
		for(int i = 0; i < n; i++) {
			vector<int> opa = ask(i);
			if(opa == good) return i;
		}
	}
	set<int> s;
	for(int i = 0; i < 350; i++) {
		int pos = rnd(n);
		if(s.count(pos)) continue;
		s.insert(pos);
		// printf("%d\n", pos);
		vector<int> opa = ask(pos);
		base = max(base, opa[0]+opa[1]);
	}
	// for(int i = 0; i < min(475, n); i++) {
	// 	vector<int> opa = ask(i);
	// 	// if(opa == good) return i;
	// 	if(opa[0]+opa[1] >= base)
	// 		base = opa[0]+opa[1];
	// }
	vector<int> a;
	for(int i = 0; i < n; i++)
		a.pb(i);
	return solve(a, 0, 0);
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:107:6: warning: unused variable 'last' [-Wunused-variable]
  107 |  int last = 0;
      |      ^~~~

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