Submission #1201323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201323		MinaRagy06	Finding Routers (IOI20_routers)	C++20	100 / 100	3 ms	584 KiB

routers

#include <bits/stdc++.h>
#ifdef MINA
#include "grader.cpp"
#endif
#include "routers.h"
using namespace std;
#define ll long long
#define SZ(x) (int) x.size()

const int L = 100'005;
int mem[L];
int query(int x) {
	if (mem[x] != -1) {
		return mem[x];
	}
	return mem[x] = use_detector(x);
}
vector<int> find_routers(int len, int n, int q) {
	memset(mem, -1, sizeof mem);
	vector<int> p = {0};
	array<int, 2> mn = {int(1e9), -1};
	for (int b = 1; b <= len; b++) {
		mn = min(mn, (array<int, 2>) {(n - SZ(p)) * (__lg(b) + 2) + len / b, b});
	}
	int b = mn[1];
	for (int st = 1; st <= len && SZ(p) < n;) {
		int en = min(st + b - 1, len);
		if (en < p.back() + 1) {
			st = en + 1;
			continue;
		}
		if (SZ(p) < n && (en == len || query(en) >= SZ(p))) {
			int l = p.back() + 1, r = en;
			while (l <= r) {
				int md = ((l + r) >> 1);
				if (query(md) >= SZ(p)) {
					r = md - 1;
				} else {
					l = md + 1;
				}
			}
			l--;
			p.push_back(2 * l - p.back());
			st = p.back() + 1;
		} else {
			st = en + 1;
		}
		mn = {int(1e9), -1};
		for (int x = 1; (x - 1) * (x - 1) <= len; x++) {
			mn = min(mn, (array<int, 2>) {(n - SZ(p)) * (__lg(x) + 2) + (len - st + 1) / x, x});
		}
		b = mn[1];
	}
	return p;
}

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