Submission #1210155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210155		ansori	Hack (APIO25_hack)	C++17	0 / 100	204 ms	4020 KiB

hack

#include "hack.h"
#include <vector>
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int B = 31623;
const int inf = 1e9;
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);
}
ll query(vector<int> a , vector<int> b){
	set<int> st;
	for(auto to : a) st.insert(to);
	for(auto to : b) st.insert(to);
	vector<ll> q;
	for(auto to : st) q.push_back(to);
	return collisions(q);
}
int hack(){	
	vector<int> a , b;
	for(int i = 1;i <= B; ++ i) a.push_back(i);
	for(int i = B; i <= inf + B; i += B) b.push_back(i);
	while(a.size() > 1 or b.size() > 1){
		//cout << a.size() << ' ' << b.size() << '\n';
		int sa = a.size() , sb = b.size();
		int ma = sa / 2 , mb = sb / 2; 
		if(a.size() > b.size()){
			vector<int> c;
			for(int i = 0;i < ma; ++ i) c.push_back(a[i]);
			if(query(c , b)) a = c;
			else{
				reverse(a.begin() , a.end());
				while(ma --) a.pop_back();
			}
		}
		else{
			vector<int> c;
			for(int i = 0;i < mb; ++ i) c.push_back(b[i]);
			if(query(c , a)) b = c;
			else{
				reverse(b.begin() , b.end());
				while(mb --) b.pop_back();
			}
		}
	}
	ll d = abs(a.front() - b.front());
	ans = inf;
	//cout << d << ' ';
	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: 0 / 8
• Subtask 2: 0 / 17
• Subtask 3: 0 / 75