Submission #1216336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216336		anfi	Hack (APIO25_hack)	C++20	100 / 100	82 ms	964 KiB

hack

#include"hack.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
const long long inf = 1e9;

int ans(int l, int r){
    while(l < r){
        int m = (r+l)>>1;
        int c = sqrt(m-l+1);
        vector<int> q;
        for(int i = 1; i <= c; i++) q.push_back(i);
        for(int i = c+l; i <= m; i += c) q.push_back(i);
        if(m+1 > c) q.push_back(m+1);
        if(collisions(q)) r = m;
        else l = m+1;
    }
    vector<int> a,pr;
    for(int i = 2; i*i <= l; i++){
        if(l%i == 0){
            a.push_back(i);
            if(i*i <= l){
                if(i*i != l) a.push_back(l/i);
            }
        }
    }
    sort(a.begin(), a.end());
    for(int p : a){
        bool cek = 1;
        for(int d : pr){
            if(p%d == 0){
                cek = 0; break;
            }
        }
        if(cek) pr.push_back(p);
    }
    int invl = -1;
    while(l != invl){
        invl = l;
        for(auto &p : pr){
            if((l/p)*p == l && collisions({1, (l/p)+1})){
                l /= p; break;
            }
        }
    }
    return l;
}

signed hack(){
    return ans(inf/2, inf);
}

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