제출 #1291345

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291345		LolkasMeep	Hack (APIO25_hack)	C++20	78.10 / 100	160 ms	79588 KiB

hack

#include "hack.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

bool didInit = false;

const ll MAX = 1000000;
const ll X = 9999998;
ll countt[MAX + 8] = {0};
// ll zero = 1;

vector<ll> query(X);

void init(){
    // for(ll n = 2; n <= MAX; n+=2){
    //     zero = lcm(zero, n);
    // }

    for(ll n = 2; n <= MAX; n+=2){
        ll h = X/(n/2);
        ll c = n*h*(h-1)/4 + (h)*(X%(n/2));
        countt[n] = c;
    }

    for(ll n = 3; n <= MAX; n+=2){
        ll h = X/n;
        ll c = n*h*(h-1)/2 + (h)*(X%(n));
        countt[n] = c;
    }

    for(ll i = 0; i < X; i++){
        query[i] = i*2+2;
    }

    didInit = true;

    // cout << "zero: " << zero << '\n';
}

bool smallOrEq(ll n){
    vector<ll> q;
    ll nSq = sqrt(n);
    for(ll x = 1; x <= nSq; x++) q.push_back(x);
    for(ll x = nSq+1; x < n+1; x+=nSq) q.push_back(x);
    q.push_back(n+1);

    ll ans = collisions(q) > 0;

    // cout << n << ": " << ans << '\n';
    
    return ans;
}

bool soE(ll l, ll r){
    vector<ll> q;
    ll d = r - l + 1;
    ll dSq = sqrt(d);

    for(ll x = 1; x <= dSq; x++){
        q.push_back(x);
    }

    for(ll x = max(dSq, l)+1; x < r+1; x+=dSq){
        q.push_back(x);
    }

    q.push_back(r+1);

    ll ans = collisions(q) > 0;

    // cout << "l: " << l << " r: "<< r << "- " << ans << '\n';
    
    return ans; 
}

int hack(){
    ll low = 2;
    ll high = 1000000001;

    while(high - low > 1){
        // cout << '\n';
        ll mid = low + (high - low) / 2 - 1;
        // cout << "l: " << low << " h: " << high << '\n';
        if(soE(low, mid)) high = mid + 1;
        else low = mid + 1;
    }
    
    return low;
}

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