Submission #1193610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193610		LucaLucaM	The Big Prize (IOI17_prize)	C++20	20 / 100	24 ms	1988 KiB

prize

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

std::mt19937 rng(123);

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

std::pair<int, int> query(int i) {
	if (memo[i].first != -1) {
		return memo[i];
	}
	auto aux = ask(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) {
	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;
			}
		}
	}

	std::vector<int> cand;

	auto get = [&](auto &self, int l, int r, int count) -> void {
		if (count == 0 || l > r) {
			return;
		}


		if (r - l <= 2) {
			for (int i = l; i < r && count; i++) {
				if (!is_max(i)) {
					cand.push_back(i);
					count--;
				}
			}
			if (count) {
				cand.push_back(r);
			}
			return;
		}

		int mid = l + rng() % (r - l + 1);
		
		while (l <= r && !is_max(l)) {
			cand.push_back(l++);
		}
		while (r >= l && !is_max(r)) {
			cand.push_back(r--);
		}
		if (l > r) {
			return;
		}
		
		int split_left = mid;
		int split_right = mid;
		while (split_left >= l && !is_max(split_left)) {
			cand.push_back(split_left++);
		}
		while (split_right <= r && !is_max(split_right)) {
			cand.push_back(split_right++);
		}

		std::pair<int, int> L, SL, SR, R;

		if (l + 1 < split_left) {
			L = query(l);
			SL = query(split_left);
			self(self, l + 1, split_left - 1, SL.first - L.first);
		}
		if (split_right < r) {
			SR = query(split_right);
			R = query(r);
			self(self, split_right + 1, r - 1, R.first - SR.first);
		}
		return;

		// int mid = l + rng() % (r - l + 1);
		// if (is_max(mid)) {
		// 	if (query(mid).first < countLeft) {
		// 		countLeft = 0;
		// 		countRight = 0;
		// 	}
		//   self(self, l, mid - 1, total_less(mid) - countLeft - countRight, countLeft, query(mid).second - countRight);
		//   self(self, mid + 1, r, total_less(mid) - countLeft - countRight, query(mid).first - countLeft, countRight);
		// } else {
		// 	int st, dr;
		// 	st = mid - query(mid).first;
		// 	dr = n - mid - 1 - query(mid).second;
		// 	self(self, l, mid - 1, );
		// }

		// return cand;

		// int aux = mid;
		// while (mid <= r && !is_max(mid)) {
		// 	cand.push_back(mid);
		// 	mid++;
		// }

		// int split_left = aux;
		// int split_right = mid;
		// self(self, l, split_left - 1, query(mid1).first);
	};

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

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

	get(get, 0, n - 1, countnonmax);

	std::sort(cand.begin(), cand.end());
	cand.erase(std::unique(cand.begin(), cand.end()), cand.end());
	
	for (int i = 0; i < (int) cand.size(); i++) {
		if (total_less(cand[i]) == 0) {
			return cand[i];
		}
	}
}

Compilation message (stderr)

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

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