Submission #1221564

#TimeUsernameProblemLanguageResultExecution timeMemory
1221564steveonalexHack (APIO25_hack)C++20
0 / 100
84 ms1220 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned int ul; typedef unsigned long long ull; #define MASK(i) (1ULL << (i)) #define GETBIT(mask, i) (((mask) >> (i)) & 1) #define ALL(v) (v).begin(), (v).end() ll max(ll a, ll b){return (a > b) ? a : b;} ll min(ll a, ll b){return (a < b) ? a : b;} ll gcd(ll a, ll b){return __gcd(abs(a), abs(b));} ll lcm(ll a, ll b){return abs(a) / gcd(a, b) * abs(b);} ll LASTBIT(ll mask){return (mask) & (-mask);} int pop_cnt(ull mask){return __builtin_popcountll(mask);} int ctz(ull mask){return __builtin_ctzll(mask);} int logOf(ull mask){return 63 - __builtin_clzll(mask);} mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);} template <class T1, class T2> bool maximize(T1 &a, T2 b){ if (a < b) {a = b; return true;} return false; } template <class T1, class T2> bool minimize(T1 &a, T2 b){ if (a > b) {a = b; return true;} return false; } template <class T> void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){ for(auto item: container) out << item << separator; out << finish; } template <class T> void remove_dup(vector<T> &a){ sort(ALL(a)); a.resize(unique(ALL(a)) - a.begin()); } #include "hack.h" int get_collision(vector<ll> x){ for(auto &i: x) i++; return collisions(x); } int find_dih(int x){ vector<int> divisor; for(int i = 1; i * i <= x; ++i) { if (x % i == 0){ divisor.push_back(i); divisor.push_back(x / i); } } remove_dup(divisor); for(int i: divisor) if (get_collision({0, i})) return i; return -1; } vector<ll> make_arr(int s, int len, int step){ vector<ll> cur; for(int i = 0; i < len; ++i) cur.push_back(s + i * step); return cur; } int find_lesser_mod(){ const int MOD = 179; vector<ll> first_shot; for(int i = 0; i < MOD; ++i) first_shot.push_back(i); for(int i = 1; i < MOD; ++i) first_shot.push_back(i * MOD); if (get_collision(first_shot) == 0) return -1; int l = 1, r = MOD * MOD; while(l < r){ int mid = (l + r) >> 1; vector<ll> cur; cur.push_back(0); for(int i = l; i <= mid; ++i) cur.push_back(i); if (get_collision(cur)) r = mid; else l = mid + 1; } return find_dih(l); } vector<ll> express_range(int l, int r){ int s = sqrt(r - l + 1); vector<ll> ans; for(int i = 0; i < s; ++i) ans.push_back(i); for(int i = r; i >= l; i -= s){ ans.push_back(i); if (i - (s - 1) <= l) break; } return ans; } int hack(){ int less_mod = find_lesser_mod(); if (less_mod != -1) return less_mod; int l = 5e8 + 1, r = 1e9; while(l < r){ int mid = (l + r) >> 1; vector<ll> S = express_range(l, mid); if (get_collision(S)) r = mid; else l = mid + 1; } return find_dih(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...