Submission #1209596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209596		zipdang04	Rotating Lines (APIO25_rotate)	C++20	Compilation error	0 ms	0 KiB

rotate

#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 = 37'300;
    vector<ll> testPool; ll countCollisions;
    unordered_set<ll> used;
    void buildTestPool() {
        used.clear();
        testPool.resize(POOL_SIZE);
        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) > 0)
                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() {
        int cnt = 0;
        do { buildTestPool(); countCollisions = collisions(testPool); cnt++;} 
        while (countCollisions == 0);
        cerr << cnt << '\n';

        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)

rotate.cpp:1:10: fatal error: hack.h: No such file or directory
    1 | #include "hack.h"
      |          ^~~~~~~~
compilation terminated.