Submission #1245224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245224		PlayVoltz	Hack (APIO25_hack)	C++20	100 / 100	82 ms	1852 KiB

hack

#include "hack.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

const int BLK = 28000;

signed hack(){
	int n, v, c=2;
	vector<int> a, b;
	for (int i=1; i<=BLK; ++i)a.pb(i);
	for (int i=500000000/BLK*BLK; i<=1000000000+BLK; i+=BLK)b.pb(i);
	if (!collisions({1, 1+(1000000000/BLK+1)*BLK})){
		while (a.size()>1||b.size()>1){
			if (a.size()<b.size())swap(a, b);
			vector<int> l, r, temp;
			for (int i=0; i<a.size()/2; ++i)l.pb(a[i]);
			for (int i=a.size()/2; i<a.size(); ++i)r.pb(a[i]), temp.pb(a[i]);
			for (auto c:b)temp.pb(c);
			if (collisions(temp))a=r;
			else a=l;
		}
		n=abs(a[0]-b[0]), v=n;
	}
	else n=(1000000000/BLK+1)*BLK, v=n;
	vector<int> vect;
	while (c*c<=v){
		if (!(v%c))v/=c, vect.pb(c);
		else ++c;
	}
	if (v!=1)vect.pb(v);
	for (auto c:vect)if (collisions({1, n/c+1}))n/=c;
	return n;
}

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