Submission #1193662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193662		LucaLucaM	The Big Prize (IOI17_prize)	C++20	20 / 100	26 ms	2412 KiB

prize

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <random>
#include "prize.h"
#include <set>

std::mt19937 rng(123);

std::vector<std::pair<int, int>> memo;
std::set<int> cand;

int queries = 0;
int answer = -1;

std::pair<int, int> query(int i) {
	if (memo[i].first != -1) {
		return memo[i];
	}
	queries++;
	if (queries > 10000) {
	  assert(false);
		assert((int) cand.size() >= 500);
	}
	auto aux = ask(i);
	if (aux[0] == 0 && aux[1] == 0) {
		answer = i;
	}
	return memo[i] = std::pair<int, int>{aux[0], aux[1]};
}

int total_less(int i) {
	return query(i).first + query(i).second;
}

int countnonmax;

bool is_max(int i) {
	if (total_less(i) == 0) {
		answer = i;
	}
	return total_less(i) == countnonmax;
}

int find_best(int n) {
	memo.resize(n, std::pair<int, int>{-1, -1});

	if (n <= 5000) {
		for (int i = 0; i < n; i++) {
			if (total_less(i) == 0) {
				return i;
			}
		}
	}

	auto get = [&](auto &self, int l, int r, int countLeft) { // countLeft = cate sunt bune in [0, l)
		if (l == r) {
			return l;
		}
		int mid = (l + r) / 2;
		int p = mid;
		while (p >= l && answer == -1 && !is_max(p)) {
			cand.insert(p--);
		}
		if (answer != -1) {
			return -1;
		}
		if (p < l) {
			return l;
		}
		int st = query(p).first;
		// std::cout << " ! " << l << ' ' << r << ' ' << p << ' ' << st << '\n';
		if (st == countLeft) {
			if (p != mid) { // stiu sigur ca p + 1 e bun
				return p + 1;
			} else { // siu ca in [l..mid] nu e niciunul bun 
				return self(self, mid + 1, r, st);
			} 
		} else {
			return self(self, l, p, countLeft);
		}
	};

	int p1 = rng() % n;
	int p2 = rng() % n;
	int p3 = rng() % n;
	int p4 = rng() % n;

	countnonmax = std::max({total_less(p1), total_less(p2), total_less(p3), total_less(p4)});

	int l = 0, r = n - 1;
	while (!is_max(l)) {
		cand.insert(l++);
	}	
	while (!is_max(r)) {
		cand.insert(r--);
	}

	// stiu ca l si r sunt max
	while (query(r).first > query(l).first) {
		int p = get(get, l + 1, r - 1, query(l).first);
		if (p == -1) {
			return answer;
		}
		// std::cout << " ? " << l << ' ' << r << ' ' << p << '\n';
		while (!is_max(p) && answer == -1) {
			cand.insert(p++);
		}
		if (answer != -1) {
			return answer;
		}
		l = p;
	}

	for (int x : cand) {
		if (total_less(x) == 0) {
			return x;
		}
	}
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:121:1: warning: control reaches end of non-void function [-Wreturn-type]
  121 | }
      | ^

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