Submission #1209435

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209435		khanhphucscratch	Hack (APIO25_hack)	C++20	25 / 100	885 ms	16456 KiB

hack

#include "hack.h"
#include<bits/stdc++.h>
#define int long long
using namespace std;
int ansn;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int rnd(int l, int r)
{
    int x = rng()%(r-l+1);
    return x+l;
}
/*int collisions(vector<int> a)
{
    map<int, int> f;
    for(int i : a) f[i%ansn]++;
    int ans = 0;
    for(pair<int, int> i : f) ans += i.second * (i.second-1)/2;
    return ans;
}*/
int32_t hack()
{
    //Subtask 1;
    vector<int> question;
    int A = 1e6;
    for(int i = A; i < 2*A; i++) question.push_back(i);
    int x = collisions(question);
    int l = 1, r = A, ans = 0;
    while(l <= r){
        int mid = (l+r)/2;
        int add = A/mid, val = mid * add * (add-1)/2;
        val += (A%mid)*add;
        //cerr<<"A"<<mid<<" "<<x<<" "<<val<<endl;
        if(val == x){ans = mid; break;}
        else if(val > x) l = mid+1;
        else r = mid-1;
    }
    return ans;
}
/*signed main()
{
    cin>>ansn;
    cout<<hack();
}*/

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