Submission #1253798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253798		antonn	Hack (APIO25_hack)	C++20	78.10 / 100	137 ms	1284 KiB

hack

#include "hack.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

template<typename T>
bool assign_min(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool assign_max(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

bool check(int l, int r) {
    int x = sqrt(r - l);
    vector<ll> v;
    for (int i = 1; i <= x; i++) {
        v.push_back(i);
    }
    for (int i = l; i < r; i += x) {
        v.push_back(i);
    }
    v.push_back(r);
    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());
    return collisions(v) != 0;
}

int hack() {
    int l = 1, r = 1e9 + 1, sol = 0;
    while (r - l > 1) {
        int m = (l + r) / 2;
        // cout << "! " << l << " " << m << " => " << check(l, m) << "\n";
        if (check(l, m)) {
            r = m;
        } else {
            l = m;
        }
    }
    return l;
}

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