Submission #1193771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193771		chaeryeong	Finding Routers (IOI20_routers)	C++20	97.52 / 100	1 ms	328 KiB

routers

#include "routers.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<int> find_routers(int l, int n, int q) {
	if (n == 2) {
		int L = 1, R = l, ans = -1;
		while (L <= R) {
			int mid = (L + R) / 2;
			if (use_detector(mid) == 0) {
				L = mid + 1; ans = mid;
			} else {
				R = mid - 1;
			}
		}
		return {0, 2 * ans};
	}
	vector <int> ret;
	ret.push_back(0);
	int B = 1;
	for (int i = 2; i <= l; i++) {
		int x = (l + i - 1) / i + n * __lg(i + 1);
		int y = (l + B - 1) / B + n * __lg(B + 1);
		if (x < y) {
			B = i;
		}
	}
	for (int i = 1; i <= l; i += B) {
		if (use_detector(min(l, i + B - 1)) == (int)ret.size() - 1) {
			continue;
		}
		int cur = max(i, ret.back());
		while (cur <= min(l, i + B - 1)) {
			int L = cur, R = min(l, cur + B - 1), ans = -1;
			while (L <= R) {
				int mid = (L + R) / 2;
				if (mid < 0 || mid > l) exit(0);
				if (use_detector(mid) > (int)ret.size() - 1) {
					R = mid - 1; ans = mid;
				} else {
					L = mid + 1;
				}
			}
			if (ans == -1) {
				break;
			}
			int v = ans - ret.back() - 1;
			ret.push_back(ret.back() + 2 * v);
			cur = ret.back() + 1;
		}
	}
	return ret;
}

• Subtask 1: 16 / 16
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 37.52 / 40