Submission #1206896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206896		am_aadvik	Hack (APIO25_hack)	C++20	25 / 100	1806 ms	24280 KiB

hack

#include <iostream>
#include <vector>
#define int long long
using namespace std;

long long collisions(vector<int> x);
int calc(vector<int> arr, int n, int ans = 0) {
	vector<int> a(n);
	for (auto x : arr)
		ans += a[x % n], ++a[x % n];
	return ans;
}
int hack() {
	vector<int> a;
	for (int i = 1; i <= 1e6; ++i) a.push_back(i);
	int s = 1, e = 1e6, res = collisions(a);
	while (s <= e) {
		int n = (s + e) / 2;
		int x = calc(a, n);
		if (x == res) return n;
		if (x < res) e = n - 1;
		else s = n + 1;
	}
	return -1;
}

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