Submission #1213635

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

hack

#include <bits/stdc++.h>

long long collisions(std::vector<long long> x);

int hack() {
  int l = 5e8, r = 1e9;
  while (l < r) {
    int m = std::midpoint(l, r);
    int b = std::sqrt(m - l + 1);
    std::vector<long long> q;
    for (int i = 1; i <= b; ++i) {
      q.push_back(i);
    }
    for (int i = l + b; i <= m; i += b) {
      q.push_back(i);
    }
    if (m + 1 > b) {
      q.push_back(m + 1);
    }
    if (collisions(q)) {
      r = m;
    } else {
      l = m + 1;
    }
  }
  auto divisors = [](int x) {
    std::vector<int> ans;
    for (int i = 1; i * i <= x; ++i) {
      if (x % i == 0) {
        ans.push_back(i);
        if (i * i != x) {
          ans.push_back(x / i);
        }
      }
    }
    std::sort(ans.begin(), ans.end());
    return ans;
  };
  for (auto &i : divisors(l)) {
    if (collisions({1, i + 1})) {
      return i;
    }
  }
  return -1;
}

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