Submission #1210928

#TimeUsernameProblemLanguageResultExecution timeMemory
1210928sqrtxsunlightHack (APIO25_hack)C++20
99.90 / 100
61 ms968 KiB
#include "hack.h" #include <bits/stdc++.h> using namespace std; bool dntm (int l, int a, int b) { vector <long long> v_ask; for (int i = 1; i <= a; i ++) v_ask.push_back (i); for (int i = a + l; i <= a * b + l; i += a) v_ask.push_back (i); return collisions (v_ask); } bool check_inside (int l, int r) { int dif = r - l; int d = sqrt (dif + 1); if (dntm (l, d, d)) return true; dif -= d * d; if (dif < 0) return false; d = sqrt (dif) + 1; return dntm (r - d * d + 1, d, d); } int hack() { int le = 5e8, ri = 1e9; while (le < ri) { int mid = (le + ri) / 2; if (check_inside (le, mid)) ri = mid; else le = mid + 1; } vector <int> divs; for (int i = 2; i * i < le; i ++) { if (le % i == 0) { divs.push_back (i); divs.push_back (le / i); } } sort (divs.begin (), divs.end ()); divs.push_back (le); int l = 0, r = divs.size () - 1; while (l < r) { int mid = (l + r) / 2; vector <long long> v_ask = {1}; for (int i = l; i <= mid; i ++) v_ask.push_back (divs[i] + 1); if (collisions (v_ask)) r = mid; else l = mid + 1; } return divs[l]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...