QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#744807#8177. Sum is Integer.5 ulp (Maxim Plyushkin, Egor Belousov, Maxim Inyutin)WA 0ms3548kbC++20911b2024-11-13 23:32:372024-11-13 23:32:39

Judging History

This is the latest submission verdict.

  • [2024-11-13 23:32:39]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3548kb
  • [2024-11-13 23:32:37]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

constexpr uint64_t mod1 = 8676756377673475627, mod2 = 8568685678567567687, bnd = 3e10;
constexpr int N = 1e5 + 2;

auto& add(auto&& a, auto b, auto mod) { return a -= (a += b) >= mod? mod: 0; }
auto& mul(auto&& a, auto b, auto mod) { return a = a * __uint128_t(b) % mod; }
uint64_t fpow(uint64_t a, uint64_t b, uint64_t mod, uint64_t r = 1) { for (; b; b /= 2, mul(a, a, mod)) if (b % 2) mul(r, a, mod); return r; }

int main() {
  uint64_t ps1 = bnd, ps2 = bnd, ans{};
  map<uint64_t, int> m{{ps1 / bnd + ps2 / bnd * bnd, 1}};
  int n; cin >> n;
  for (int i = 0; i < n; ++i) {
    int p, q; cin >> p >> q;
    add(ps1, fpow(q, mod1 - 2, mod1, p), mod1);
    add(ps2, fpow(q, mod2 - 2, mod2, p), mod2);
    auto t = ps1 / bnd + ps2 / bnd * bnd;
    ans += m[t - 1] + m[t - bnd] + m[t - 1 - bnd];
    ++m[t];
  }
  cout << ans << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3548kb

input:

4
1 6
1 3
1 2
1 2

output:

0

result:

wrong answer 1st words differ - expected: '2', found: '0'