제출 #1267115

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1267115		Ak_16	Hack (APIO25_hack)	C++20	78.10 / 100	124 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);
            }
            if((r-l)/2>=sq*(sq+1)&&sq>0){
                x.push_back(l+sq*sq+sq+1);
            }
            if((r-l)/2!=sq*sq&&(r-l)/2!=sq*(sq+1)){
                x.push_back((r+l+2)/2);
            }
            long long col = collisions(x);
            if(col==0LL){
                l = (r+l)/2+1;
            }
            else{
                r=(r+l)/2;
            }
    }
    return l;

}

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