Submission #1300069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300069		farica	Hack (APIO25_hack)	C++20	25 / 100	983 ms	16476 KiB

hack

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

using namespace std;
using ll = long long;
using vi = vector<ll>;


const int R = 1e6;

ll f(ll N) {
	ll r = R % N, k = R / N;
	ll ans = 1LL * r * k * (k+1) / 2;
	ans += 1LL * (N-r) * k * (k-1) / 2;
	return ans;
}

int hack(){
	int l=1, r=R;
	vi v;
	for(int i=1; i<=R; ++i) v.push_back(i);
	ll x = collisions(v);
	while(l < r) {
		int mid = (l+r)/2;
		if(f(mid) == x) return mid;
		if(f(mid) > x) l = mid+1;
		else r = mid-1;
	}

    return r;
}

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