QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#510256 | #4942. Robust Defense | ideograph_advantage | WA | 3094ms | 6896kb | C++20 | 7.1kb | 2024-08-09 00:41:59 | 2024-08-09 00:42:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0);
#define iter(a) a.begin(), a.end()
#define pb emplace_back
#define ff first
#define ss second
#define SZ(a) int(a.size())
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#ifdef zisk
void debug(){cerr << "\n";}
template<class T, class ... U> void debug(T a, U ... b){cerr << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cerr << *l << " ", l++;
cerr << "\n";
}
#else
#define debug(...) void()
#define pary(...) void()
#endif
template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
return o << '(' << p.ff << ',' << p.ss << ')';
}
using ld = ll;
using pdd = pll;
#define X first
#define Y second
pdd operator+(pdd a, pdd b)
{ return {a.X + b.X, a.Y + b.Y}; }
pdd operator-(pdd a, pdd b)
{ return {a.X - b.X, a.Y - b.Y}; }
pdd operator*(ld i, pdd v)
{ return {i * v.X, i * v.Y}; }
pdd operator*(pdd v, ld i)
{ return {i * v.X, i * v.Y}; }
pdd operator/(pdd v, ld i)
{ return {v.X / i, v.Y / i}; }
ld dot(pdd a, pdd b)
{ return a.X * b.X + a.Y * b.Y; }
ld cross(pdd a, pdd b)
{ return a.X * b.Y - a.Y * b.X; }
ld abs2(pdd v)
{ return v.X * v.X + v.Y * v.Y; };
ld abs(pdd v)
{ return sqrt(abs2(v)); };
int sgn(ld v)
{ return v > 0 ? 1 : (v < 0 ? -1 : 0); }
// int sgn(ld v){ return v > eps ? 1 : ( v < -eps ? -1 : 0); }
int ori(pdd a, pdd b, pdd c)
{ return sgn(cross(b - a, c - a)); }
bool collinearity(pdd a, pdd b, pdd c)
{ return ori(a, b, c) == 0; }
bool btw(pdd p, pdd a, pdd b)
{ return collinearity(p, a, b) && sgn(dot(a - p, b - p)) <= 0; }
bool seg_intersect(pdd p1, pdd p2, pdd p3, pdd p4){
if(btw(p1, p3, p4) || btw(p2, p3, p4) || btw(p3, p1, p2) || btw(p4, p1, p2))
return true;
return ori(p1, p2, p3) * ori(p1, p2, p4) < 0 &&
ori(p3, p4, p1) * ori(p3, p4, p2) < 0;
}
pdd intersect(pdd p1, pdd p2, pdd p3, pdd p4){
ld a123 = cross(p2 - p1, p3 - p1);
ld a124 = cross(p2 - p1, p4 - p1);
return (p4 * a123 - p3 * a124) / (a123 - a124);
}
pdd perp(pdd p1)
{ return pdd(-p1.Y, p1.X); }
pdd projection(pdd p1, pdd p2, pdd p3)
{ return p1 + (p2 - p1) * dot(p3 - p1, p2 - p1) / abs2(p2 - p1); }
pdd reflection(pdd p1, pdd p2, pdd p3)
{ return p3 + perp(p2 - p1) * cross(p3 - p1, p2 - p1) / abs2(p2 - p1) * 2; }
pdd linearTransformation(pdd p0, pdd p1, pdd q0, pdd q1, pdd r) {
pdd dp = p1 - p0, dq = q1 - q0, num(cross(dp, dq), dot(dp, dq));
return q0 + pdd(cross(r - p0, num), dot(r - p0, num)) / abs2(dp);
} // from line p0--p1 to q0--q1, apply to r
// -1: a // b (if same), 0/1: a < b
int cmp(pll a, pll b, bool same = true, pll dir = pll(1, 0)){
#define is_neg(k) (cross(dir, k) < 0 || (cross(dir, k) == 0 && dot(dir, k) < 0))
int A = is_neg(a), B = is_neg(b);
if(A != B)
return A < B;
if(sgn(cross(a, b)) == 0)
return same ? abs2(a) < abs2(b) : -1;
return sgn(cross(a, b)) > 0;
}
const ll MOD = 998244353;
ll inv(ll a) {
ll b = MOD - 2;
ll ans = 1;
while (b > 0) {
if (b & 1) ans = ans * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return ans;
}
int main(){
StarBurstStream;
int n, m, S;
cin >> m >> n >> S;
S = S * inv(100) % MOD;
ll D = (1 - S + MOD) % MOD;
vector<pll> recv(m);
for (int i = 0; i < m; i++)
cin >> recv[i].X >> recv[i].Y;
vector<pll> pts(n);
for (int i = 0; i < n; i++)
cin >> pts[i].X >> pts[i].Y;
vector<ll> spow(n + 1), invspow(n + 1);
vector<ll> dpow(n + 1), invdpow(n + 1);
spow[0] = 1; invspow[0] = 1;
dpow[0] = 1; invdpow[0] = 1;
for (int i = 1; i <= n; i++) {
spow[i] = spow[i - 1] * S % MOD, invspow[i] = inv(spow[i]);
dpow[i] = dpow[i - 1] * D % MOD, invdpow[i] = inv(dpow[i]);
}
sort(iter(pts), [&](pll x, pll y) {
return x.Y != y.Y ? x.Y < y.Y : x.X < y.X;
});
vector good(n, vector<bool>(n, true));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (pll p : recv)
if (ori(pts[i], pts[j], p) < 0) good[i][j] = false;
}
}
// all points are distinct
// cnt[i][j] = # of point k s.t. strictly above ij, and i < k < j
// cnt2[i][j] = # of points k s.t. strictly in ij
vector cnt(n, vector<int>(n)), cnt2(n, vector<int>(n));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++){
if (pts[i] >= pts[j]) continue;
for (int k = 0; k < n; k++) {
if (pts[i] < pts[k] && pts[k] < pts[j]) {
int tmp = ori(pts[i], pts[j], pts[k]);
if (tmp > 0) cnt[i][j]++; // only for i < j
else if (tmp == 0) cnt2[i][j]++, cnt2[j][i]++;
}
}
}
debug("cnt");
for (int i = 0; i < n; i++) pary(iter(cnt[i]));
debug("cnt2");
for (int i = 0; i < n; i++) pary(iter(cnt2[i]));
auto calc_tri = [&](array<int, 3> arr) { // strictly inside
sort(iter(arr), [&](int x, int y){ return pts[x] < pts[y]; });
auto [x, y, z] = arr;
int tmp = ori(pts[x], pts[y], pts[z]);
if (tmp == 0) return 0;
else if (tmp < 0) return cnt[x][z] - cnt[x][y] - cnt[y][z] - cnt2[x][y] - cnt2[y][z] - 1;
else return cnt[x][y] + cnt[y][z] - cnt[x][z] - cnt2[x][z];
};
auto getvec = [&](pii x) {
return pts[x.ss] - pts[x.ff];
};
pary(iter(pts));
ll ans = 0;
auto solve = [&](int bottom) {
debug("solve", bottom, pts[bottom]);
pll O = pts[bottom];
vector<pii> trans;
for (int j = bottom + 1; j < n; j++) {
for (int k = bottom + 1; k < n; k++) {
if (ori(O, pts[j], pts[k]) <= 0) continue;
if (!good[j][k]) continue;
trans.pb(pii(j, k));
}
}
sort(iter(trans), [&](pii x, pii y) -> bool{
int tmp = cmp(getvec(x), getvec(y), false);
if (tmp != -1) return tmp;
pll v = getvec(x);
return dot(v, pts[x.ff]) > dot(v, pts[y.ff]);
});
vector<ll> dp(n);
for (int j = bottom + 1; j < n; j++) {
if (!good[bottom][j]) continue;
debug("init trans", j, "cnt", cnt2[bottom][j], "+ 2");
dp[j] = invdpow[cnt2[bottom][j] + 2] * S % MOD * S % MOD;
}
for (auto [i, j] : trans) {
debug("normal trans", i, j, "cnt", calc_tri({bottom, i, j}), cnt2[i][j], cnt2[bottom][j], "+ 1");
dp[j] += dp[i] * invdpow[calc_tri({bottom, i, j}) + 1 + cnt2[i][j] + cnt2[bottom][j]] % MOD * S % MOD;
dp[j] %= MOD;
}
for (int j = bottom + 1; j < n; j++) {
if (!good[j][bottom]) continue;
debug("end trans", j, dp[j]);
ans += dp[j];
ans %= MOD;
}
};
for(int i = 0; i < n; i++) solve(i);
ans *= dpow[n];
ans %= MOD;
cout << ans << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
input:
1 4 50 0 0 -1 0 3 0 0 1 2 -1
output:
686292993
result:
ok single line: '686292993'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
3 5 20 3 0 1 3 5 3 0 0 0 6 6 0 6 6 3 3
output:
771443236
result:
ok single line: '771443236'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
1 2 3 4 5 7 9 -2 -3
output:
184375732
result:
ok single line: '184375732'
Test #4:
score: 0
Accepted
time: 2799ms
memory: 6896kb
input:
500 500 47 7 19 16 17 20 13 1 10 17 9 5 23 12 2 15 12 16 8 11 8 8 12 3 2 11 13 23 0 3 23 13 10 9 12 11 5 8 18 6 0 6 20 3 9 1 21 13 18 5 11 9 15 8 17 6 18 1 8 4 24 7 14 11 11 2 9 8 9 23 3 17 15 21 10 19 7 13 16 0 10 0 7 6 17 11 9 9 4 1 15 21 12 1 24 20 7 21 7 20 0 10 3 3 24 2 12 18 11 20 5 14 20 10 4...
output:
963504722
result:
ok single line: '963504722'
Test #5:
score: 0
Accepted
time: 3094ms
memory: 6660kb
input:
1 500 55 59773527 -48622950 -76633359 443117719 441925049 713512931 -994603144 -68987280 772876381 722131762 511352639 621437284 -136059566 -211230774 -558357374 -936479782 64380588 -111294401 841774806 594567294 515039746 -199627032 -376709851 386524480 -254296132 210052025 -824608562 909197921 118...
output:
185827470
result:
ok single line: '185827470'
Test #6:
score: -100
Wrong Answer
time: 2609ms
memory: 6868kb
input:
1 500 14 20 11 3 8 10 19 3 14 8 14 10 18 19 8 20 10 0 21 11 15 18 10 6 1 1 13 20 8 12 12 13 5 16 13 3 21 4 13 19 17 8 18 21 0 19 3 1 8 3 15 15 0 12 21 5 13 22 6 14 4 21 16 7 4 20 16 17 7 13 2 16 11 9 12 22 16 2 9 21 1 15 12 1 5 20 19 2 4 8 19 17 19 19 19 4 22 8 7 21 18 0 7 13 19 20 2 18 22 10 13 1 1...
output:
36085402
result:
wrong answer 1st lines differ - expected: '682068131', found: '36085402'