Submission #1291158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291158		LolkasMeep	Hack (APIO25_hack)	C++20	25 / 100	838 ms	23888 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 = 999000;
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';
}

int hack(){
    if(!didInit) init();

    // for(ll i = 0; i < X; i++) query[i] = i*2+2;
    ll c = collisions(query);
    ll ans1 = -1;
    ll ans2 = -1;

    // cout << "c: " << c << '\n';

    for(ll i = 2; i <= MAX; i++){
        if(countt[i] == c){
            // cout << "ping: " << i << ' ' << c << '\n';
            if(ans1 == -1) ans1 = i;
            else ans2 = i;
        }
    }

    if(collisions({ans1, ans1*2}) > 0) return ans1;
    else return ans2;
    
    return 1;
}

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