Submission #1210849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210849		ansori	Hack (APIO25_hack)	C++17	98 / 100	175 ms	2952 KiB

hack

#include "hack.h"
#include <vector>
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int B = 27480;
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 = (inf / 2 / B) * 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> la;
			vector<int> ra;
			for(int i = 0;i < ma; ++ i) la.push_back(a[i]);
			for(int i = ma;i < sa; ++ i) ra.push_back(a[i]);
			if(query(ra , b)) a = ra;
			else a = la;
		}
		else{
			vector<int> lb;
			vector<int> rb;
			for(int i = 0;i < mb; ++ i) lb.push_back(b[i]);
			for(int i = mb;i < sb; ++ i) rb.push_back(b[i]);
			if(query(lb , a)) b = lb;
			else b = rb;
		}
	}
	ll d = abs(a.front() - b.front());
	ans = inf;
	//cout << d << ' ';
	for(ll i = 1;i * i <= d; ++ i){
		if(d % i == 0){
			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: 72.9716 / 75