Submission #45532080

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
#include<atcoder/all>
using mint1 = atcoder::dynamic_modint<1>;
using mint2 = atcoder::dynamic_modint<2>;

random_device rd;
mt19937 mt(rd());

int random_prime(){
    while (true){
        int pr = mt() % 100000000 + 900000000;
        if (atcoder::internal::is_prime_constexpr(pr)){
            return pr;
        }
    }
}
uniform_real_distribution<long double> dist(0.0,1.0);

int main(){
    mint1::set_mod(random_prime());
    mint2::set_mod(random_prime());
    int n; cin >> n;
    map<ull,ll> cnt;
    auto get_hash = [&](mint1 h1, mint2 h2){
        return (ull(h1.val()) << 32) + ull(h2.val());
    };
    ld geta = dist(mt);
    ld sum = geta;
    mint1 rui1 = 0;
    mint2 rui2 = 0;
    cnt[0] = 1;
    for (int i = 0; i < n; i++){
        ll p, q; cin >> p >> q;
        sum += ld(p)/ld(q);
        rui1 += mint1(p) / mint1(q);
        rui2 += mint2(p) / mint2(q);
        ll seisu = (ll)floor(sum);
        mint1 syosu1 = rui1 - seisu;
        mint2 syosu2 = rui2 - seisu;
        cnt[get_hash(syosu1,syosu2)]++;
    }
    ll ans = 0;
    for (auto [syosu, c] : cnt){
        ans += c * (c-1) / 2;
    }
    cout << ans << endl;
}

Submission Info

Submission Time
Task M - Sum is Integer
User noya2
Language C++ 20 (gcc 12.2)
Score 100
Code Size 1318 Byte
Status AC
Exec Time 207 ms
Memory 16164 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 63
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt
All handmade-01.txt, handmade-02.txt, handmade-03.txt, handmade-04.txt, handmade-05.txt, handmade-06.txt, handmade-07.txt, handmade-08.txt, handmade-09.txt, handmade-10.txt, handmade-11.txt, handmade-12.txt, handmade-13.txt, handmade-14.txt, handmade-15.txt, handmade-16.txt, handmade-17.txt, handmade-18.txt, handmade-19.txt, handmade-20.txt, handmade-21.txt, handmade-22.txt, handmade-23.txt, handmade-24.txt, handmade-25.txt, handmade-26.txt, handmade-27.txt, handmade-28.txt, handmade-29.txt, handmade-30.txt, random1-01.txt, random1-02.txt, random1-03.txt, random1-04.txt, random1-05.txt, random1-06.txt, random1-07.txt, random1-08.txt, random1-09.txt, random1-10.txt, random2-01.txt, random2-02.txt, random2-03.txt, random2-04.txt, random2-05.txt, random3-01.txt, random3-02.txt, random3-03.txt, random3-04.txt, random3-05.txt, random4-01.txt, random4-02.txt, random4-03.txt, random4-04.txt, random4-05.txt, random5-01.txt, random5-02.txt, random5-03.txt, random5-04.txt, random5-05.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
handmade-01.txt AC 93 ms 3688 KiB
handmade-02.txt AC 98 ms 3864 KiB
handmade-03.txt AC 109 ms 4780 KiB
handmade-04.txt AC 122 ms 6628 KiB
handmade-05.txt AC 149 ms 9720 KiB
handmade-06.txt AC 172 ms 13048 KiB
handmade-07.txt AC 199 ms 15952 KiB
handmade-08.txt AC 197 ms 16164 KiB
handmade-09.txt AC 199 ms 16116 KiB
handmade-10.txt AC 177 ms 13876 KiB
handmade-11.txt AC 177 ms 14376 KiB
handmade-12.txt AC 172 ms 13036 KiB
handmade-13.txt AC 165 ms 12984 KiB
handmade-14.txt AC 128 ms 12252 KiB
handmade-15.txt AC 99 ms 10480 KiB
handmade-16.txt AC 38 ms 6696 KiB
handmade-17.txt AC 184 ms 15240 KiB
handmade-18.txt AC 163 ms 14324 KiB
handmade-19.txt AC 202 ms 16048 KiB
handmade-20.txt AC 4 ms 3568 KiB
handmade-21.txt AC 48 ms 3620 KiB
handmade-22.txt AC 37 ms 3624 KiB
handmade-23.txt AC 14 ms 3528 KiB
handmade-24.txt AC 125 ms 15152 KiB
handmade-25.txt AC 79 ms 10012 KiB
handmade-26.txt AC 87 ms 12380 KiB
handmade-27.txt AC 93 ms 3532 KiB
handmade-28.txt AC 2 ms 3696 KiB
handmade-29.txt AC 2 ms 3616 KiB
handmade-30.txt AC 2 ms 3728 KiB
random1-01.txt AC 12 ms 3920 KiB
random1-02.txt AC 29 ms 3868 KiB
random1-03.txt AC 52 ms 3932 KiB
random1-04.txt AC 12 ms 3984 KiB
random1-05.txt AC 7 ms 3872 KiB
random1-06.txt AC 13 ms 3896 KiB
random1-07.txt AC 19 ms 3884 KiB
random1-08.txt AC 26 ms 3992 KiB
random1-09.txt AC 12 ms 3772 KiB
random1-10.txt AC 38 ms 3816 KiB
random2-01.txt AC 89 ms 10536 KiB
random2-02.txt AC 163 ms 15164 KiB
random2-03.txt AC 59 ms 8672 KiB
random2-04.txt AC 118 ms 12576 KiB
random2-05.txt AC 75 ms 9700 KiB
random3-01.txt AC 166 ms 14364 KiB
random3-02.txt AC 81 ms 9536 KiB
random3-03.txt AC 110 ms 11208 KiB
random3-04.txt AC 194 ms 15384 KiB
random3-05.txt AC 35 ms 6248 KiB
random4-01.txt AC 2 ms 3616 KiB
random4-02.txt AC 2 ms 3652 KiB
random4-03.txt AC 2 ms 3532 KiB
random4-04.txt AC 2 ms 3760 KiB
random4-05.txt AC 2 ms 3664 KiB
random5-01.txt AC 207 ms 15976 KiB
random5-02.txt AC 203 ms 16052 KiB
random5-03.txt AC 201 ms 16008 KiB
random5-04.txt AC 205 ms 15948 KiB
random5-05.txt AC 205 ms 15928 KiB
sample-01.txt AC 1 ms 3560 KiB
sample-02.txt AC 1 ms 3560 KiB
sample-03.txt AC 1 ms 3664 KiB