QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#755066#9521. Giving Directions in HarbinANIG#WA 0ms3672kbC++141.9kb2024-11-16 16:23:062024-11-16 16:23:08

Judging History

你现在查看的是最新测评结果

  • [2024-11-16 16:23:08]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3672kb
  • [2024-11-16 16:23:06]
  • 提交

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
*/

详细

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)