Submission #1208665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208665		k1r1t0	Hack (APIO25_hack)	C++20	100 / 100	95 ms	1184 KiB

hack

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll collisions(vector<ll> x);

const int T = 500;

int hack() {
	vector<ll> group;
	for (int i = 1; i <= T; i++)
		group.push_back(i);
	for (int i = 1; i <= T; i++)
		group.push_back(T + T * i);
	if (collisions(group)) {
		int l = 1, r = (int)(1e6);
		while (l < r) {
			int mid = (l + r) / 2;
			int S = sqrt(mid - l + 1);
			vector<ll> pts;
			for (int i = 1; i <= S; i++)
				pts.push_back(i);
			for (int i = mid + 1; i > max(l, S); i -= S)
				pts.push_back(i);
			if (collisions(pts)) r = mid;
			else l = mid + 1;
		}
		return l;
	}
	int l = (int)(4.95e8), r = (int)(1e9);
	while (l < r) {
		int mid = (l + r) / 2;
		int S = sqrt(mid - l + 1);
		vector<ll> pts;
		for (int i = 1; i <= S; i++)
			pts.push_back(i);
		for (int i = mid + 1; i > max(l, S); i -= S)
			pts.push_back(i);
		if (collisions(pts)) r = mid;
		else l = mid + 1;
	}
	vector<int> ff;
	int t = l;
	for (int d = 2; d * d <= t; d++)
		while (t % d == 0) {
			ff.push_back(d);
			t /= d;
		}
	if (t > 1)
		ff.push_back(t);
	int ans = l;
	if (!ff.empty()) {
		for (int x : ff)
			if (collisions({1, 1 + ans / x}))
				ans /= x;
	}
	return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 17 / 17
• Subtask 3: 75 / 75