Submission #1209388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209388		zipdang04	Hack (APIO25_hack)	C++20	25 / 100	1069 ms	23896 KiB

hack

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

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;
    }
}
int hack(){
    Subtask1::buildCollisions();
    std::vector<long long> all(Subtask1::MAX);
    std::iota(all.begin(), all.end(), 1);
    return Subtask1::getBucket(collisions(all));
}

Compilation message (stderr)

hack.cpp: In function 'int Subtask1::getBucket(long long int)':
hack.cpp:28:17: warning: division by zero [-Wdiv-by-zero]
   28 |         return 1/0;
      |                ~^~

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