Submission #1366937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1366937		Cebrayil09	Hack (APIO25_hack)	C++20	8 / 100	2250 ms	69344 KiB

hack

#include "hack.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long

int hack() {
    ll cur = 1;
    ll l = 1;

    vector<ll> v;

    while(1) {
        map<ll,int> m;
        ll c = 0;

        while(c <= 1000000) {
            v.push_back(cur);
            if(cur%l != 0) m[cur%l]++;

            c += m[cur%l];

            m[cur%l]++;
            cur++;
        }
        v.pop_back();
        v.pop_back();
        cur -= 2;

        int res = collisions(v);
        if(!res) {
            l = v.back();
            continue;
        }

        ll r = v.back() - 1;
        while(l <= r) {
            ll mid = l + (r-l)/2;

            vector<int> cnt(mid);

            c = 0;
            for(ll &i : v) {
                c += cnt[i%mid];
                cnt[i%mid]++;
            }

            if(c == res) return mid;

            if(c > res) l = mid+1;
            else r = mid-1;
        }
        exit(0);
    }
}

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