Submission #1220573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220573		rainboy	Hack (APIO25_hack)	C++20	78.10 / 100	128 ms	1116 KiB

hack

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

using namespace std;

const int N = 1000000000;

typedef vector<long long> vl;

bool check(int l, int r) {
	int m = 1;
	while (m * m < r - l)
		m++;
	int q = (r - l + 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) + l, r);
	return collisions(aa) != 0;
}

int hack() {
	int lower = 1, upper = N + 1;
	while (upper - lower > 1) {
		int n = (lower + upper) / 2;
		if (check(lower, n))
			upper = n;
		else
			lower = n;
	}
	return lower;
}

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