제출 #1219455

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219455		ppssbb09	Hack (APIO25_hack)	C++20	99.40 / 100	51 ms	924 KiB

hack

#include "hack.h"
#include <vector>
#include <bits/stdc++.h>

using namespace std;
using lld = long long int;

int hack() {

	lld l = 500000002;
	lld r = 1000000001;
	lld sum = 0;
	while (l + 1 < r) {
		for (lld i = 0; i < (lld)log2(r - l + 1); i++) {
			lld sq = ceil(sqrt((r - l) / 2));
			vector<lld> x(sq * 2);
			for (lld j = 0; j < sq; j++) {
				x[j] = j + 1;
			}
			for (lld j = 0; j < sq; j++) {
				x[sq + j] = l + (sq) * (j + 1) - 1;
			}
			lld col = collisions(x);
			if (col) {
				r = x[sq * 2 - 1];
			}
			else l = x[sq * 2 - 1] + 1;
			sum += sq * 2;
		}
	}

	lld col;
	if (collisions({ 1, l })) col = l - 1;
	else col = l;

	for (lld i = 2; i <= sqrt(col); i++) {
		if (col % i == 0) {
			if (collisions({ 1, i + 1 })) return i;
		}
	}
	for (lld i = sqrt(col); i >= 2; i--) {
		if (col % i == 0) {
			if (collisions({ 1, (col / i) + 1 })) return col / i;
		}
	}
	
	return col;
}

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