제출 #1361786

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1361786		opeleklanos	Hack (APIO25_hack)	C++20	25 / 100	774 ms	24304 KiB

hack

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#include "hack.h"

#define ll long long

ll secretNum = 938572;

ll queries = 0;

// ll collisions(vector<ll> v){
//     queries+=v.size();
//     vector<ll> newV(secretNum +1, 0);
//     ll ans = 0;
//     for(auto i : v){
//         ans += newV[i%secretNum];
//         newV[i%secretNum] ++;
//     }

//     return ans;
// }

ll findAns(ll k){
    ll s = 1000000/k;
    ll ans = k * (s*(s-1)/2);
    ans += s * (1000000%k);
    return ans;
}

vector<ll> ansForBucketI(1000001, -1);
int hack(){

    if(ansForBucketI[3] == -1){
        for(ll i = 2; i<=1000000; i++){
            ansForBucketI[i] = findAns(i);
        }
        reverse(ansForBucketI.begin(), ansForBucketI.end());
    }

    vector<ll> v;
    for(int i = 1; i<= 1000000; i++) v.push_back(i);
    ll ans = collisions(v);

    return 1000000 - (lower_bound(ansForBucketI.begin(), ansForBucketI.end(), ans) - ansForBucketI.begin());
}

• 서브태스크 0: 0 / 0
• 서브태스크 1: 8 / 8
• 서브태스크 2: 17 / 17
• 서브태스크 3: 0 / 75