Submission #1366908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1366908		atharva_a_b	Hack (APIO25_hack)	C++17	25 / 100	784 ms	16088 KiB

hack

#include "hack.h"
#include <cstdint>
#include <vector>

long long f(int32_t mid, const int32_t& Q) {
    long long g = Q/mid, r = Q%mid;

    return (r*(g*(g+1)/2))+((mid-r)*((g-1)*g/2));
}

int hack() {
    const int32_t Q = 1'000'000;

    std::vector<long long> x(Q);
    int32_t i = 0;
    while(i < Q) {
        x[i] = i+1;
        ++i;
    }

    long long C = collisions(x), c;

    int32_t l = 1, r = Q, mid;

    while(l <= r) {
        mid = (l+r)/2;
        c = f(mid, Q);

        if(c == C) return mid;
        if(c > C) {
            l = mid+1;
        } else {
            r = mid-1;
        }
    }

    return -1;
}

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