Submission #1206121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206121		lighton	Hack (APIO25_hack)	C++20	0 / 100	6 ms	956 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 f= 1;
    while(f) {
        f=0;
        for (int i = 2; i * i <= m; i++) {
            if (m % i) continue;
            vector<ll> v;
            v.pb(1), v.pb(m / i + 1);
            if (collisions(v)) {
                m /= i;
                ans /= i;
                f=1;
                break;
            }
        }
    }
    return ans;
}

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