QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#755330 | #9530. A Game On Tree | ANIG# | WA | 0ms | 3728kb | C++14 | 4.0kb | 2024-11-16 17:04:40 | 2024-11-16 17:04:41 |
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 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) {
cout << "ADD:V:" << x << endl;
dv(a[x], b[x]);
cout << "MUL_ST:" << endl;
for (int i = 0;i <= m;i++) cout << g[i] << " "; cout << endl;
(a[x] += ni) %= mod; (b[x] -= ni) %= mod;
cout << a[x] <<" " << b[x] << endl;
for (int i = 0;i <= m;i++) {
f[i] = b[x]*g[i]%mod;
if (i) (f[i] += a[x]*g[i-1]) %= mod;
}
for (int i = 0;i <= m;i++) cout << f[i] << " "; cout << endl;
cout << "MUL_END\n";
}
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;
cout << "CHECK:" << i << " " << s[i].t.p << " " << s[i].t.q << " " << g[m/2] << endl;
}
if (ans < 0) ans += mod;
ans = ans*ni%mod;
cout << ans;
return 0;
}
/*
3 3
-4 -5 -6
1 2 3
DIV:
1 0 0 0
0 1
1 0 0 0
DIV_END
CHECK:1 4 3 0
DIV:
1 0 0 0
0 1
1 0 0 0
DIV_END
CHECK:2 5 3 0
DIV:
1 0 0 0
0 1
1 0 0 0
DIV_END
CHECK:3 4 2 0
DIV:
1 0 0 0
0 1
1 0 0 0
DIV_END
CHECK:4 6 3 0
ADD:V:3
DIV:
1 0 0 0
0 1
1 0 0 0
DIV_END
MUL_ST:
1 0 0 0
333333336 -333333335
-333333335 333333336 0 0
MUL_END
ADD:V:3
DIV:
-333333335 333333336 0 0
333333336 -333333335
1 0 0 0
DIV_END
MUL_ST:
1 0 0 0
666666672 -666666671
-666666671 666666672 0 0
MUL_END
ADD:V:3
DIV:
-666666671 666666672 0 0
666666672 -666666671
1 0 0 0
DIV_END
MUL_ST:
1 0 0 0
1 0
0 1 0 0
MUL_END
DIV:
0 1 0 0
0 1
0 1 0 0
DIV_END
CHECK:5 5 2 1
DIV:
0 1 0 0
0 1
0 1 0 0
DIV_END
CHECK:6 6 2 1
ADD:V:2
DIV:
0 1 0 0
0 1
0 1 0 0
DIV_END
MUL_ST:
0 1 0 0
333333336 -333333335
0 -333333335 333333336 0
MUL_END
ADD:V:2
DIV:
0 -333333335 333333336 0
333333336 -333333335
0 1 0 0
DIV_END
MUL_ST:
0 1 0 0
666666672 -666666671
0 -666666671 666666672 0
MUL_END
ADD:V:2
DIV:
0 -666666671 666666672 0
666666672 -666666671
0 1 0 0
DIV_END
MUL_ST:
0 1 0 0
1 0
0 0 1 0
MUL_END
DIV:
0 0 1 0
0 1
0 0 1 0
DIV_END
CHECK:7 4 1 0
DIV:
0 0 1 0
0 1
0 0 1 0
DIV_END
CHECK:8 5 1 0
DIV:
0 0 1 0
0 1
0 0 1 0
DIV_END
CHECK:9 6 1 0
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3728kb
input:
2 3 1 2 2 3 5 1 2 1 5 3 2 4 2
output:
DIV: 1 0 0 0 1 1 0 0 DIV_END CHECK:1 -2 2 0 DIV: 1 0 0 0 1 1 0 0 DIV_END CHECK:2 -2 3 0 DIV: 1 0 0 0 1 1 0 0 DIV_END CHECK:3 -1 2 0 ADD:V:1 DIV: 1 0 0 0 1 1 0 0 DIV_END MUL_ST: 1 0 0 0 500000004 -500000003 -500000003 500000004 0 0 MUL_END ADD:V:1 DIV: -500000003 500000004 0 500000004 -50...
result:
wrong answer 1st lines differ - expected: '443664158', found: 'DIV:'