Submission #1209539

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209539		zipdang04	Hack (APIO25_hack)	C++20	0 / 100	112 ms	656 KiB

hack

#include "hack.h"
#include <bits/stdc++.h>
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
*/

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template <class T> using PQMax = priority_queue<T>;
template <class T> using PQMin = priority_queue<T, vector<T>, greater<T>>;
template <class T1, class T2>
void maximize(T1 &a, T2 b){
    if (b > a) a = b;
}
template <class T1, class T2>
void minimize(T1 &a, T2 b){
    if (b < a) a = b;
}
template <class T>
void read(T &number)
{
    bool negative = false;
    register int c;
    number = 0;
    c = getchar();
    while (c != '-' && !isalnum(c)) c = getchar();
    if (c=='-'){
        negative = true;
        c = getchar();
    }
    for (; (c>47 && c<58); c=getchar())
        number = number *10 + c - 48;
    if (negative)
        number *= -1;
}
template <class T, class ...Ts>
void read(T &a, Ts& ... args){
    read(a);
    read(args...);
}

/*
struct Node
{
    int node, len;
    Node() {node = len = 0;}
    Node(int node, int len) {this -> node = node, this -> len = len;}
};
typedef vector<Node> vg;
*/

#define fi first
#define se second

#define FOR(type, i, a, b) for(type i = (a); i <= (b); i++)
#define REV(type, i, b, a) for(type i = (b); i >= (a); i--)

#define testBit(n, bit) (((n) >> (bit)) & 1)
#define flipBit(n, bit) ((n) ^ (1ll << (bit)))
#define cntBit(n) __builtin_popcount(n)
#define cntBitll(n) __builtin_popcountll(n)
#define log2(n) (31 - __builtin_clz(n))
#define log2ll(n) (63 - __builtin_clzll(n))
#define CURRENT_TIMESTAMP chrono::steady_clock::now().time_since_epoch().count()
#define randomize mt19937_64 mt(CURRENT_TIMESTAMP)

randomize;
struct rnd{
    inline static ll next(ll n) {return mt() % n;}
    inline static ll next(ll l, ll r) {return l + next(r-l+1);}
};

namespace Subtask1{
    constexpr int MAX = 1'000'000;
    long long collisions[MAX + 1] = {};

    void buildCollisions() {
        for (int n = 1; n <= MAX; n++) {
            int r = MAX % n, q = MAX / n;
            collisions[n] 
                = 1ll * r * (q+1) * q / 2
                + 1ll * (n-r) * q * (q-1) / 2;
	    }
    }

    int getBucket(long long number) {
        int lo = 1, hi = MAX;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (collisions[mid] == number)
                return mid;
            if (collisions[mid] > number)
                lo = mid + 1;
            else
                hi = mid - 1;
        }
        return 1/0;
    }
}
namespace Subtask3{
    const int POOL_SIZE = 10'000;
    vector<ll> testPool; ll countCollisions;
    void buildTestPool() {
        testPool.resize(POOL_SIZE);
        unordered_set<ll> used;
        for (ll &num: testPool)
            do{
                num = rnd::next(1'000'000'000'000ll);
            } while (used.find(num) != used.end());
    }
    int findFirst() {
        int lo = 0, hi = POOL_SIZE - 1, ans = -1;
        vector<ll> tmp = testPool;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            while (tmp.size() > mid + 1) tmp.pop_back();

            if (collisions(tmp) == countCollisions)
                ans = mid, hi = mid-1;
            else {
                FOR(int, i, mid + 1, hi) tmp.push_back(testPool[i]);
                lo = mid + 1;
            }
        }
        // cerr << ans << '\n';
        assert(ans != -1);
        return ans;
    }
    int findSecond(int first) {
        FOR(int, i, 0, first)
            if (collisions({testPool[i], testPool[first]}))
                return i;
        return 1 / 0;
    }

    bool test(ll d) {
        return collisions({1, d + 1}) != 0;
    }
    
    int solve() {
        do { buildTestPool(); countCollisions = collisions(testPool); } 
        while (countCollisions == 0);

        int p1 = findFirst(), p2 = findSecond(p1);
        ll num = abs(testPool[p1] - testPool[p2]);
        // cerr << num << ' ' << p1 << ' ' << p2 << '\n';
        
        ll answer = num;
        for (ll d = 1; d * d <= num; d++) {
            if (num % d != 0) continue;

            // cerr << d << ' ' << test(d) << '\n';
            if (test(d)) {minimize(answer, d); break;}
            // cerr << num / d << ' ' << test(num / d) << '\n';
            if (test(num / d)) minimize(answer, num / d);
        }
        return answer;
    }
}

int hack(){
    // Subtask1::buildCollisions();
    // std::vector<long long> all(Subtask1::MAX);
    // std::iota(all.begin(), all.end(), 1);
    // return Subtask1::getBucket(collisions(all));

    return Subtask3::solve();
}

Compilation message (stderr)

hack.cpp: In function 'void read(T&)':
hack.cpp:29:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   29 |     register int c;
      |                  ^
hack.cpp: In function 'int Subtask1::getBucket(long long int)':
hack.cpp:103:17: warning: division by zero [-Wdiv-by-zero]
  103 |         return 1/0;
      |                ~^~
hack.cpp: In function 'int Subtask3::findSecond(int)':
hack.cpp:139:18: warning: division by zero [-Wdiv-by-zero]
  139 |         return 1 / 0;
      |                ~~^~~

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