Submission #1267109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267109		Ak_16	Hack (APIO25_hack)	C++20	78.10 / 100	72 ms	1284 KiB

hack

#include "hack.h"
#include <vector>
using namespace std;
#define ll long long

int sqrt(int k){
    ll le=0;
    ll ri=k;
    ll ans = k+1;
    while(le<=ri){
        ll mi = (le+ri)/2;
        if(mi*mi<=k){
            le=mi+1;
            ans=mi;
        }
        else{
            ri = mi-1;
        }
    }
    return ans;
}

int hack(){
    vector<long long> x;
    int l=2;
    int r=1000000000;

    while(l<r){
            int sq = sqrt((r-l)/2);
            x.clear();
            for(int i=1; i<=sq+1; i++){
                x.push_back(i);
            }
            x.push_back(sq+l+1);
            for(int i=1; i<=sq-1; i++){
                x.push_back(sq+l+1+sq*i);
            }
            long long col = collisions(x);
            if(col==0LL){
                l = l+sq*sq+1;
            }
            else{
                r=l+sq*sq;
            }
    }
    return l;

}

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