Submission #1215040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215040		thunopro	Hack (APIO25_hack)	C++20	25 / 100	1159 ms	16452 KiB

hack

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

const int N = 1e6 ; 
ll calc(int mid) {
    ll total = 0;
    int base = N / mid;
    int rem  = N % mid;
    for (int i = 1; i <= mid; i++) {
        ll x = base + (i <= rem ? 1 : 0);
        total += x * (x - 1ll) / 2;
    }
    return total;
}

int hack () 
{
	vector<ll> v ; 
	for ( int i = 1 ; i <= N ; i ++ ) v . push_back (i) ; 
	ll result = collisions ( v ) ; 
	int l = 1 , r = 1e6 ; 
	int res = 0 ; 
	while ( l <= r ) 
	{
		int mid = (l+r)/2 ; 
		if ( calc (mid) >= result ) l = mid + 1 , res = mid ; 
		else r = mid - 1 ; 
	}
	return res ; 
}

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