QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#314218 | #8177. Sum is Integer | ucup-team2303# | WA | 74ms | 13360kb | C++17 | 2.1kb | 2024-01-25 14:31:41 | 2024-01-25 14:31:41 |
Judging History
answer
// #pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define PB emplace_back
#define int long long
#define ll long long
#define vi vector<int>
#define siz(a) ((int) ((a).size()))
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
void print(vi n) { rep(i, 0, siz(n) - 1) cerr << n[i] << " \n"[i == siz(n) - 1]; }
const int N = 2e5;
int a;
long double t[N + 5];
map<pair<int, int>, int> mp;
struct s1 {
const int mod = 1e9 + 7;
int s[N + 5], inv[N + 5], tmp;
void init() {
tmp = 1;
rep(i, 1, N) (tmp *= i) %= mod;
inv[0] = inv[1] = 1;
rep(i, 2, N) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
rep(i, 1, N) (inv[i] *= tmp) %= mod;
}
void ins(int i, int x, int y) {
// cout << inv[y] << endl;
s[i] = (s[i - 1] + x * inv[y] % mod) % mod;
}
int get(int i, int x) {return (s[i] - x * tmp % mod + mod) % mod;}
} s1;
struct s2 {
const int mod = 998244353;
int s[N + 5], inv[N + 5], tmp;
void init() {
tmp = 1;
rep(i, 1, N) (tmp *= i) %= mod;
inv[0] = inv[1] = 1;
rep(i, 2, N) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
rep(i, 1, N) (inv[i] *= tmp) %= mod;
}
void ins(int i, int x, int y) {
s[i] = (s[i - 1] + x * inv[y] % mod) % mod;
}
int get(int i, int x) {return (s[i] - x * tmp % mod + mod) % mod;}
} s2;
signed main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> a;
mp[{0, 0}] = 1;
int ans = 0, x, y;
s1.init(), s2.init();
rep(i, 1, a) {
cin >> x >> y;
t[i] = t[i - 1] + 1.0 * x / y;
s1.ins(i, x, y);
s2.ins(i, x, y);
x = t[i];
rep(j, x - 10, x + 10) if(mp.count({s1.get(i, j), s2.get(i, j)}))
ans += mp[{s1.get(i, j), s2.get(i, j)}];
// cout << ans << endl;
++mp[{s1.get(i, x), s2.get(i, x)}];
}
// cout << s1.s[1] << endl;
cout << ans;
return cerr << endl << 1.0 * clock() / CLOCKS_PER_SEC << endl, 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 8ms
memory: 10388kb
input:
4 1 6 1 3 1 2 1 2
output:
2
result:
ok "2"
Test #2:
score: 0
Accepted
time: 4ms
memory: 10080kb
input:
5 1 1 2 2 3 3 4 4 5 5
output:
15
result:
ok "15"
Test #3:
score: 0
Accepted
time: 4ms
memory: 10104kb
input:
2 1 99999 99999 100000
output:
0
result:
ok "0"
Test #4:
score: -100
Wrong Answer
time: 74ms
memory: 13360kb
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'