QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#755228#9530. A Game On TreeANIG#WA 0ms3664kbC++142.8kb2024-11-16 16:46:572024-11-16 16:46:57

Judging History

This is the latest submission verdict.

  • [2024-11-16 16:46:57]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3664kb
  • [2024-11-16 16:46:57]
  • Submitted

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 dv (int a, int b) {
    if (b == 0) {
        int na = qpow(a); 
        for (int i = 0;i <= m;i++) g[i] = f[i+1]*na%mod; 
        return; 
    }
    // cout << "DIV:\n"; 
    // for (int i = 0;i <= n;i++) cout << f[i] << " "; cout << endl;  
    int sx = 0, bi = qpow(b);
    // cout << a << " " << b << endl; 
    for (int i = 0;i <= m;i++) {
        (sx = f[i]-sx) %= mod; 
        g[i] = sx*bi%mod; 
        sx = g[i]*a%mod; 
    }
    // for (int i = 0;i <= n;i++) cout << g[i] << " "; cout << endl; 
    // cout << "DIV_END\n"; 
}
void add (int x) {
    dv(a[x], b[x]); 
    (a[x] += ni) %= mod; (b[x] -= ni) %= mod;
    for (int i = 0;i <= m;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]++;
            }
        }
        dv(a[s[i].id], b[s[i].id]);
        (ans += g[m/2]*(s[i].t.p*qpow(s[i].t.q)%mod)%mod) %= mod; 
    }
    if (ans < 0) ans += mod; 
    ans = ans*ni%mod;
    cout << ans;
    return 0; 
}
/*
3 3
-4 -5 -6
1 2 3

2 3
-4 -5
1 2 3
DIV:
1 0 0 
0 1
1 0 0 
DIV_END
DIV:
1 0 0 
0 1
1 0 0 
DIV_END
DIV:
1 0 0 
0 1
1 0 0 
DIV_END
DIV:
-500000003 500000004 0 
500000004 -500000003
1 0 0 
DIV_END
DIV:
0 1 0 
0 1
0 1 0 
DIV_END
DIV:
0 1 0 
0 1
0 1 0 
DIV_END
DIV:
0 1 0 
0 1
0 1 0 
DIV_END
DIV:
0 -500000003 500000004 
500000004 -500000003
0 1 0 
DIV_END
DIV:
0 0 1 
0 1
0 0 1 
DIV_END
DIV:
0 0 1 
0 1
0 0 1 
DIV_END
500000008
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
3
1 2
2 3
5
1 2
1 5
3 2
4 2

output:

433333336

result:

wrong answer 1st lines differ - expected: '443664158', found: '433333336'