Submission #1204998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204998		Kel_Mahmut	Hack (APIO25_hack)	C++20	100 / 100	67 ms	1588 KiB

hack

#include "hack.h"
#include <vector>
#include <bits/stdc++.h>
#define pb push_back
#define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;

const int N = 1e9;
const int N2 = 5e8;
const int k = 35000;
const int b2 = N2 / k;
const int b = N / k;

int hack(){
    vector<vector<int>> s(2);
    for(int i = 1; i <= k; i++) s[0].pb(i + 1);
    for(int i = b2; i <= b + 1; i++) s[1].pb(i * k);
    function<int(vector<int>&, vector<int>&)> query = [&](vector<int>& s1, vector<int>& s2){
        vector<ll> cur;
        for(int i : s1) cur.pb(i);
        for(int i : s2) cur.pb(i);
        ll ret = collisions(cur);
        return ret > 0;
    };
    while(s[0].size() > 1 || s[1].size() > 1){
        if(s[0].size() > s[1].size()){
            vector<int> sl, sr;
            for(int i = 0; i < (int) s[0].size() / 2; i++){
                sl.pb(s[0][i]);
            }
            for(int i = (int) s[0].size() / 2; i < (int) s[0].size(); i++){
                sr.pb(s[0][i]);
            }
            if(query(sr, s[1])){
                s[0] = sr;
            }
            else{
                s[0] = sl;
            }
        }
        else{
            vector<int> sl, sr;
            for(int i = 0; i < (int) s[1].size() / 2; i++){
                sl.pb(s[1][i]);
            }
            for(int i = (int) s[1].size() / 2; i < (int) s[1].size(); i++){
                sr.pb(s[1][i]);
            }
            if(query(sl, s[0])){
                s[1] = sl;
            }
            else{
                s[1] = sr;
            }
        }
    }
    int ans = s[1][0] - s[0][0];
    int res = ans;
    for(int i = 2; i * i <= ans; i++){
        while(ans % i == 0){
            if(collisions({1ll, res / i + 1})){
                ans /= i;
                res /= i;
            }
            else
                break;
        }
        while(ans % i == 0){
            ans /= i;
        }
    }
    if(ans > 1 && collisions({1ll, (ll) res / ans + 1}))
        res /= ans;
    return res;
}

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