QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#755066 | #9521. Giving Directions in Harbin | ANIG# | WA | 0ms | 3672kb | C++14 | 1.9kb | 2024-11-16 16:23:06 | 2024-11-16 16:23:08 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 505, mod = 1e9+7;
int n, m, x[N], v[N], lt[N], a[N], b[N], f[N], ni;
struct frac {
int p, q;
friend bool operator < (const frac & a, const frac & b) {
return a.p*b.q < b.p*a.q;
}
};
struct node {
frac t; int id;
}s[N*N];
inline bool cmp (node x, node y) {
if (x.t < y.t) return 1;
if (y.t < x.t) return 0;
return x.id < y.id;
}
int qpow (int x, int y = mod-2) {
int res = 1;
while (y) {
if (y&1) res = res*x%mod;
x = x*x%mod; y >>= 1;
}
return res;
}
int g[N];
void add (int x) {
int sx = 0, bi = qpow(b[x]);
for (int i = 0;i <= n;i++) {
(sx = f[i]-sx) %= mod;
g[i] = sx*bi%mod;
sx = g[i]*a[x]%mod;
}
(a[x] += ni) %= mod; (b[x] -= ni) %= mod;
for (int i = 0;i <= n;i++) {
f[i] = b[x]*g[i]%mod;
if (i) (f[i] += a[x]*g[i-1]) %= mod;
}
}
signed main () {
cin >> n >> m; ni = qpow(n);
for (int i = 1;i <= n;i++) cin >> x[i];
sort(x+1, x+1+n);
for (int i = 1;i <= m;i++) cin >> v[i];
int st = 0;
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= m;j++) {
s[++st] = (node){-x[i], v[j], j};
}
}
sort(s+1, s+1+st, cmp);
for (int i = 1;i <= m;i++) lt[i] = 1;
for (int i = 1;i <= m;i++) a[i] = 0, b[i] = 1;
f[0] = 1;
int ans = 0;
for (int i = 1;i <= st;i++) {
for (int j = 1;j <= m;j++) {
while (lt[j] <= n && cmp((node){-x[lt[j]], v[j], j}, s[i])) {
add(j);
lt[j]++;
}
(ans += f[m/2]*(s[i].t.p*qpow(s[i].t.q)%mod)%mod) %= mod;
}
}
if (ans < 0) ans += mod;
cout << ans;
return 0;
}
/*
2 3
-4 -5
1 2 3
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3672kb
input:
1 2 S 2 E 1
output:
0
result:
wrong answer Integer parameter [name=m] equals to 0, violates the range [1, 20] (test case 1)