Submission #1213574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213574		zipdang04	Hack (APIO25_hack)	C++20	8 / 100	103 ms	1596 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);}
};

vector<ll> operator + (const vector<ll> a, const vector<ll> b) {
    vector<ll> ans(a.size() + b.size());
    int ptr = 0;
    for (ll i: a) ans[ptr++] = i;
    for (ll i: b) ans[ptr++] = i;
    return ans;
}

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 = 37'300;
    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());
    }
    pair<ll, ll> find() {
        vector<long long> all = testPool;
        
        while (all.size() > 2) {
            int mid = (int) all.size() / 2;
            vector<long long> L(all.begin(), all.begin() + mid);
            vector<long long> R(all.begin() + mid, all.end());
            // cerr << L.size() << ' ' << R.size() << '\n';
            
            if (collisions(L) > 0) all = L;
            else if (collisions(R) > 0) all = R;
            else {
                int midL = (int)L.size() / 2, midR = (int)R.size() / 2;
                vector<long long> LL(L.begin(), L.begin() + midL),
                                  LR(L.begin() + midL, L.end()),
                                  RL(R.begin(), R.begin() + midR),
                                  RR(R.begin() + midR, R.end());
                // cerr << LL.size() << ' ' << LR.size() << ' ' << RL.size() << ' ' << RR.size() << '\n';
                if (collisions(LL + RL)) all = LL + RL;
                else if (collisions(LL + RR)) all = LL + RR;
                else if (collisions(LR + RR)) all = LR + RR;
                else all = LR + RL;
            }
        }
        // cerr << ans << '\n';
        return {all[0], all[1]};
    }
    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() {
        int cnt = 0;
        do { buildTestPool(); countCollisions = collisions(testPool); cnt++;} 
        while (countCollisions == 0);

        auto [d1, d2] = find();
        ll num = abs(d1 - d2);
        // 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:111:17: warning: division by zero [-Wdiv-by-zero]
  111 |         return 1/0;
      |                ~^~
hack.cpp: In function 'int Subtask3::findSecond(int)':
hack.cpp:156:18: warning: division by zero [-Wdiv-by-zero]
  156 |         return 1 / 0;
      |                ~~^~~

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