Submission #1220713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220713		rainboy	Hack (APIO25_hack)	C++20	100 / 100	79 ms	916 KiB

hack

#include "hack.h"
#include <vector>

using namespace std;

const int N = 1000000000;

typedef vector<long long> vl;

int hack() {
	int lower = N / 2 + 1, upper = N + 1;
	while (upper - lower > 1) {
		int n = (lower + upper) / 2;
		int m = 1;
		while (m * m < n - lower)
			m++;
		int q = (n - lower + m - 1) / m;
		vl aa(m + q);
		for (int i = 0; i < m; i++)
			aa[i] = i + 1;
		for (int i = 0; i < q; i++)
			aa[m + i] = min(m * (i + 1) + lower, n);
		if (collisions(aa) == 0)
			lower = n;
		else
			upper = n;
	}
	int n = lower, n_ = n;
	for (int p = 2; p <= n_ / p; p++)
		if (n_ % p == 0) {
			while (n_ % p == 0)
				n_ /= p;
			while (n % p == 0 && collisions({ 1, n / p + 1 }) != 0)
				n /= p;
		}
	if (n_ > 1)
		if (n % n_ == 0 && collisions({ 1, n / n_ + 1 }) != 0)
			n /= n_;
	return n;
}

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