Submission #1317178

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317178		jesusarg	Hack (APIO25_hack)	C++20	0 / 100	3094 ms	1848 KiB

hack

#include <bits/stdc++.h>
#define ll long long 
#define pb push_back
#define f first
#define s second
using namespace std;

ll collisions(vector<ll> x);

ll calc(ll k, ll n) {
    ll q=k/n;
    ll r=k%n;
    return r*(q*(q+1)/2)+(n-r)*(q*(q-1)/2);
}

int hack(){
    int k= 100000; 
    vector<ll> x(k);
    for(int i=0; i<k; i++){
        x[i]=i+1;
    } 
    ll val1 = collisions(x);
    if(val1>0){
        ll lo=2, hi=k, ans=k;
        while(lo<=hi){
            ll mid = (lo+(hi-lo))>>1;
            if(calc(k,mid) >= val1){ 
                ans=mid; 
                lo=mid+1; 
            }
            else hi=mid-1;
        }
        return (int)(ans);
    }
    ll b = 1000000000000LL; 
    for(int i=0; i<k; i++){
        x[i]=(i+1)*b;
    }
    ll val2=collisions(x);
    if(val2 > 0){
        vector<ll> d;
        for(ll i = 1; i*i <= b; i++){
            if(b%i == 0){
                d.pb(i);
                if(i*i != b){
                    d.pb(b/i);
                }
            }
        }
        sort(d.begin(), d.end());
        for(auto i : d){
            if(i>1 && calc(k,i) == val2){
                return (int)(i);
            }
        }
    }
    return k;
}

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