Submission #1206132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206132		lighton	Hack (APIO25_hack)	C++20	100 / 100	53 ms	964 KiB

hack

#include "hack.h"
#include <vector>
#include<bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define forf(i,s,e) for(int i = s; i<=e; i++)
#define forb(i,s,e) for(int i = s; i>=e; i--)
#define idx(i,v) (int)(lower_bound(all(v),i)-v.begin())
#define comp(v) v.erase(unique(all(v)),v.end())
#define sz(v) (int)v.size()
#define fs first
#define se second
#define SP << " " <<
#define LN << "\n"
#define IO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
ll inf = 1e18;
ll big = 1e9;
ll piv = 10;
double r = 2;
bool chk(ll s, ll a){
    vector<ll> v;
    forf(i,1,a) v.pb(i);
    forf(i,1,a) v.pb(s+i*a);
    return collisions(v);
}

ll dnc(ll s, ll e){
    if(e-s <= piv){
        forf(i,s,e){
            vector<ll> v;
            v.pb(1), v.pb(i+1);
            if(collisions(v)) return i;
        }
    }
    ll a = 1;
    while((double)((a+1)*(a+1) - 1) < (double)(e-s)/r) a++;

    if(chk(s,a)) return dnc(s,s+a*a-1);
    else return dnc(s+a*a, e);
}

int hack(){
    int m = dnc(big/2,big);
    int ans = m;
    int rem = m;
    for (int i = 2; i * i <= m; i++) {
        if (rem % i) continue;
        vector<ll> v;
        v.pb(1), v.pb(ans / i + 1);
        while (collisions(v)) {
            ans /= i;
            if(ans % i) break;
            v.clear();
            v.pb(1), v.pb(ans / i + 1);
        }
        while(rem % i == 0) rem /= i;
    }
    if(rem != 1) {
        vector<ll> v;
        v.pb(1), v.pb(ans / rem + 1);
        while (collisions(v)) {
            ans /= rem;
            if (ans % rem) break;
            v.clear();
            v.pb(1), v.pb(ans / rem + 1);
        }
    }
    return ans;
}

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