Submission #1204838

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204838		model_code	Hack (APIO25_hack)	C++20	25 / 100	894 ms	16068 KiB

hack

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

using namespace std;

long long f(int n, int k = (int)1e6){
    int r = k % n;
    int cnt = k / n;

    long long res = 0;
    res += 1LL * r * cnt * (cnt + 1) / 2;
    res += 1LL * (n - r) * cnt * (cnt - 1) / 2;

    return res;
}

int hack(){
    int k = (int)1e6;
    vector<long long> x(k);
    iota(x.begin(), x.end(), 1);
    
    long long res = collisions(x);

    int l = 1, r = k;
    while (l <= r){
        int m = (l + r) >> 1;

        if (f(m) == res) return m;
        
        if (f(m) < res){
            r = m - 1;
        } else {
            l = m + 1;
        }
    }

    return 42;
}

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