Submission #1209747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209747		ansori	Hack (APIO25_hack)	C++20	25 / 100	682 ms	1612 KiB

hack

#include "hack.h"
#include <vector>
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 4e4 + 69;
const int inf = 1e9 + 69;
int ans;
ll collisions(vector<ll> v) ;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll n){
	ll x = rng();
	return abs(x) % n + 1;
}
void expiriment(int x){
	vector<ll> v;
	v.push_back(1);
	v.push_back(1 + x);
	if((collisions(v) == 1)) ans = min(ans , x);
}
int hack(){	
	ios_base::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	//rand rand
	vector<ll> st;
	for(int i = 0;i < N; ++ i) st.push_back(rand(1e15));
	vector<ll> vc;
	for(auto to : st) vc.push_back(to);
	//cout << collisions(vc) << ' ';
	while(st.size() > 2){
		vector<ll> v;
		for(auto to : st){
			ll x = rand(2);
			if(x <= 1) v.push_back(to); 
		}
		//cout << ' ' << collisions(v) << ' ';
		if(v.size() > 1 and (collisions(v))){
			st.clear();
			for(auto to : v) st.push_back(to);
		}
	}
	ll x = *st.begin() , y = *(--st.end());
	ll d = abs(x - y);
	//cout << d << ' ';
	ans = inf;
	for(ll i = 1;i * i <= d; ++ i){
		if(d % i == 0){
			//cout << i << ' ';
			expiriment(i);
			if(d / i != i and d / i <= 1e9) expiriment(d / i);
		}
	}
	return ans;
}

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