제출 #1206104

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1206104		ByeWorld	Hack (APIO25_hack)	C++20	100 / 100	115 ms	964 KiB

hack

#include "hack.h"
#include <bits/stdc++.h>
// #pragma GCC optimize("O3", "unroll-loops")
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
#define COL collisions
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<pii,ll> ipii;
const ll MAXN = 3e5+10;
const ll MOD = 1000000;
const ll INF = 1e9;
const ll SQRT = 6500;
const ll BL = INF/SQRT+1;
ll sum(auto a, auto b){ return (a+MOD+b)%MOD; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll bisa;

ll cek(int l, int r){
	if(l == r){
		return COL({1, 1+l});
	}
	ll len = r-l;

	ll sq = sqrt(len);
	vector<ll> vec;
	ll tot = 0, las = 1; vec.pb(1);

	while(tot+sq <= len-sq){
		las += sq;
		vec.pb(las); // sq
		tot += sq;
	}
	if(l!=1){
		las += l; //l
		vec.pb(las);
	}

	// for(auto in : vec ) cout << in <<' ';
	// 	cout << " xxx\n"; cout << tot << "\n";
	for(int i=1; i<=sq-1; i++){
		las++;
		vec.pb(las); // 1
		tot++;
	}
	if(tot != len){
		for(int i=0; i<vec.size(); i++){
			if(vec[i]==1) continue;
			vec[i] += len-tot;
		}
		vec.pb(len-tot+1);
		// las += len-tot; vec.pb(las);
	}

	// for(auto in : vec ) cout << in <<' ';
	// 	cout << " in\n";
	return COL(vec);
}

int hack(){
	int l=INF/2, r=INF, mid=0, cnt=-1;
	// cout << cek(2, 2) <<  "pp\n";
	// return 1;
	while(l<=r){
		// cout << l << ' ' << r <<" lr\n";
		mid = md;
		if(cek(l, mid)) cnt = mid, r=mid-1;
		else l = mid+1, bisa = mid;
	}

	int X = cnt;

	vector<int> coba;
	for(int i=2; i*i<=cnt; i++){
		if(X%i) continue;
		coba.pb(i);
		while(X%i == 0) X /= i;
	}
	if(X > 1) coba.pb(X);

	for(auto in : coba){
        while(cnt % in == 0 && COL({1, cnt/in + 1}) > 0)
            cnt /= in;
	}

	if(cnt==-1) assert(false);
	return cnt;
}
// jwbn sample 5, 2

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