제출 #1209432

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1209432		khanhphucscratch	Hack (APIO25_hack)	C++20	0 / 100	22 ms	16020 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 = 0; i < 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: 0 / 8
• Subtask 2: 0 / 17
• Subtask 3: 0 / 75