Submission #1256703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256703		bynix	Hack (APIO25_hack)	C++20	25 / 100	132 ms	1332 KiB

hack

#include "hack.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

ll lsqrt(ll x){
  ll l = 1, r = x;
  while (l < r){
    ll mid = (l+r)/2;
    if (mid * mid <= x) l = mid+1;
    else r = mid;
  }
  return l-1;
}

vector<ll> gen(ll x){
  ll v = lsqrt(x); 
  vector<ll> ans;
  for (int i = 1; i < v; i++) ans.push_back(i);
  for (int i = v; i <= x; i += v) ans.push_back(i);
  ans.push_back(x+1);
  return ans;
}

int hack(){
  ll l = 2, r = 1e9;
  while (l < r){
    ll mid = (l+r)/2;
    if (collisions(gen(mid)) >= 1) r = mid;
    else l =  mid + 1;
  }
  return r;
}

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