Submission #1256719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256719		bynix	Hack (APIO25_hack)	C++20	78.10 / 100	284 ms	2872 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) r = mid;
    else l = mid + 1;
  }
  return l;
}

vector<ll> gen(ll l, ll r){
  ll len = r - l + 1;
  ll v = lsqrt(len); 
  set<ll> ans;
  for (int i = 1; i <= v; i++) ans.insert(i);
  for (int i = l+v; i <= r+1; i += v) ans.insert(i);
  ans.insert(r+1);
  vector<ll> a;
  a.assign(ans.begin(), ans.end());
  return a;
}

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

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