QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#316727 | #8177. Sum is Integer | ucup-team008# | WA | 40ms | 8032kb | C++20 | 8.4kb | 2024-01-28 02:41:18 | 2024-01-28 02:41:18 |
Judging History
answer
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>
using namespace std;
// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
typedef vector<int> vi;
#define f first
#define s second
#define derr if(1) cerr
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << flush;
// END NO SAD
template<class Fun>
class y_combinator_result {
Fun fun_;
public:
template<class T>
explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args>
decltype(auto) operator()(Args &&...args) {
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
template<class T>
bool updmin(T& a, T b) {
if(b < a) {
a = b;
return true;
}
return false;
}
template<class T>
bool updmax(T& a, T b) {
if(b > a) {
a = b;
return true;
}
return false;
}
typedef int64_t ll;
struct barrett_reduction {
unsigned mod;
uint64_t div;
barrett_reduction(unsigned m) : mod(m), div(-1LLU / m) {}
unsigned operator()(uint64_t a) const {
#ifdef __SIZEOF_INT128__
uint64_t q = uint64_t(__uint128_t(div) * a >> 64);
uint64_t r = a - q * mod;
return unsigned(r < mod ? r : r - mod);
#endif
return unsigned(a % mod);
}
};
template<const int &MOD, const barrett_reduction &barrett>
struct _b_int {
int val;
_b_int(int64_t v = 0) {
if (v < 0) v = v % MOD + MOD;
if (v >= MOD) v %= MOD;
val = int(v);
}
_b_int(uint64_t v) {
if (v >= uint64_t(MOD)) v %= MOD;
val = int(v);
}
_b_int(int v) : _b_int(int64_t(v)) {}
_b_int(unsigned v) : _b_int(uint64_t(v)) {}
static int inv_mod(int a, int m = MOD) {
// https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Example
int g = m, r = a, x = 0, y = 1;
while (r != 0) {
int q = g / r;
g %= r; swap(g, r);
x -= q * y; swap(x, y);
}
return x < 0 ? x + m : x;
}
explicit operator int() const { return val; }
explicit operator unsigned() const { return val; }
explicit operator int64_t() const { return val; }
explicit operator uint64_t() const { return val; }
explicit operator double() const { return val; }
explicit operator long double() const { return val; }
_b_int& operator+=(const _b_int &other) {
val -= MOD - other.val;
if (val < 0) val += MOD;
return *this;
}
_b_int& operator-=(const _b_int &other) {
val -= other.val;
if (val < 0) val += MOD;
return *this;
}
static unsigned fast_mod(uint64_t x) {
#if !defined(_WIN32) || defined(_WIN64)
return barrett(x);
#endif
// Optimized mod for Codeforces 32-bit machines.
// x must be less than 2^32 * MOD for this to work, so that x / MOD fits in an unsigned 32-bit int.
unsigned x_high = unsigned(x >> 32), x_low = unsigned(x);
unsigned quot, rem;
asm("divl %4\n"
: "=a" (quot), "=d" (rem)
: "d" (x_high), "a" (x_low), "r" (MOD));
return rem;
}
_b_int& operator*=(const _b_int &other) {
val = fast_mod(uint64_t(val) * other.val);
return *this;
}
_b_int& operator/=(const _b_int &other) {
return *this *= other.inv();
}
friend _b_int operator+(const _b_int &a, const _b_int &b) { return _b_int(a) += b; }
friend _b_int operator-(const _b_int &a, const _b_int &b) { return _b_int(a) -= b; }
friend _b_int operator*(const _b_int &a, const _b_int &b) { return _b_int(a) *= b; }
friend _b_int operator/(const _b_int &a, const _b_int &b) { return _b_int(a) /= b; }
_b_int& operator++() {
val = val == MOD - 1 ? 0 : val + 1;
return *this;
}
_b_int& operator--() {
val = val == 0 ? MOD - 1 : val - 1;
return *this;
}
_b_int operator++(int) { _b_int before = *this; ++*this; return before; }
_b_int operator--(int) { _b_int before = *this; --*this; return before; }
_b_int operator-() const {
return val == 0 ? 0 : MOD - val;
}
friend bool operator==(const _b_int &a, const _b_int &b) { return a.val == b.val; }
friend bool operator!=(const _b_int &a, const _b_int &b) { return a.val != b.val; }
friend bool operator<(const _b_int &a, const _b_int &b) { return a.val < b.val; }
friend bool operator>(const _b_int &a, const _b_int &b) { return a.val > b.val; }
friend bool operator<=(const _b_int &a, const _b_int &b) { return a.val <= b.val; }
friend bool operator>=(const _b_int &a, const _b_int &b) { return a.val >= b.val; }
_b_int inv() const {
return inv_mod(val);
}
_b_int pow(int64_t p) const {
if (p < 0)
return inv().pow(-p);
_b_int a = *this, result = 1;
while (p > 0) {
if (p & 1)
result *= a;
p >>= 1;
if (p > 0)
a *= a;
}
return result;
}
friend ostream& operator<<(ostream &os, const _b_int &m) {
return os << m.val;
}
friend istream& operator>>(istream &is, _b_int &m) {
int64_t x;
is >> x;
m = x;
return is;
}
};
int MOD1 = int(1e9) + 7;
barrett_reduction barrett1(MOD1);
using mnum1 = _b_int<MOD1, barrett1>;
int MOD2 = 998244353;
barrett_reduction barrett2(MOD2);
using mnum2 = _b_int<MOD2, barrett2>;
mt19937 g1(0x14004);
void solve() {
int n;
cin >> n;
vector<int> p(n), q(n);
for(int i = 0; i < n; i++) cin >> p[i] >> q[i];
vector<long double> psum(n+1);
psum[0] = uniform_real_distribution<double>(0, 1)(g1);
for(int i = 1; i <= n; i++) {
psum[i] = psum[i-1] + double(p[i-1]) / q[i-1];
}
map<array<int, 2>, int> dp;
ll ret = 0;
dp[{0, 0}] = 1;
array<int, 2> curr = {0, 0};
for(int i = 0; i < n; i++) {
int lhs = (int)(mnum1(p[i]) / q[i]);
int rhs = (int)(mnum2(p[i]) / q[i]);
curr[0] += lhs; if(curr[0] >= MOD1) curr[0] -= MOD1;
curr[1] += rhs; if(curr[1] >= MOD2) curr[1] -= MOD2;
ll shift = ll(psum[i+1]) - ll(psum[i]);
curr[0] -= shift; if(curr[0] < 0) curr[0] += MOD1;
curr[1] -= shift; if(curr[1] < 0) curr[1] += MOD2;
ret += dp[curr]++;
}
cout << ret << "\n";
}
// what would chika do
// are there edge cases (N=1?)
// are array sizes proper (scaled by proper constant, for example 2* for koosaga tree)
// integer overflow?
// DS reset properly between test cases
// are you doing geometry in floating points
// are you not using modint when you should
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3568kb
input:
4 1 6 1 3 1 2 1 2
output:
2
result:
ok "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
5 1 1 2 2 3 3 4 4 5 5
output:
15
result:
ok "15"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
2 1 99999 99999 100000
output:
0
result:
ok "0"
Test #4:
score: -100
Wrong Answer
time: 40ms
memory: 8032kb
input:
200000 82781 82781 86223 86223 16528 16528 84056 84056 94249 94249 54553 54553 25943 25943 10415 10415 52417 52417 46641 46641 70298 70298 84228 84228 55441 55441 49326 49326 11753 11753 89499 89499 58220 58220 71482 71482 32373 32373 7251 7251 78573 78573 74268 74268 46682 46682 20314 20314 85519 8...
output:
19799405515
result:
wrong answer 1st words differ - expected: '10603308211', found: '19799405515'