QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#485716 | #4942. Robust Defense | PetroTarnavskyi | WA | 1340ms | 9648kb | C++20 | 4.3kb | 2024-07-21 02:24:03 | 2024-07-21 02:24:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const int mod = 998244353;
int add(int a, int b)
{
return a + b < mod ? a + b : a + b - mod;
}
void updAdd(int& a, int b)
{
a += b;
if (a >= mod)
a -= mod;
}
int sub(int a, int b)
{
return a - b >= 0 ? a - b : a - b + mod;
}
int mult(int a, int b)
{
return (LL)a * b % mod;
}
int binpow(int a, int n)
{
int res = 1;
while (n)
{
if (n & 1)
res = mult(res, a);
a = mult(a, a);
n /= 2;
}
return res;
}
struct Pt
{
int x, y;
Pt operator-(const Pt& p) const
{
return {x - p.x, y - p.y};
}
};
LL sq(const Pt& p)
{
return (LL)p.x * p.x + (LL)p.y * p.y;
}
int sgn(LL x)
{
return (0 < x) - (x < 0);
}
LL dot(const Pt& p, const Pt& q)
{
return (LL)p.x * q.x + (LL)p.y * q.y;
}
LL cross(const Pt& p, const Pt& q)
{
return (LL)p.x * q.y - (LL)p.y * q.x;
}
LL orient(const Pt& p, const Pt& q, const Pt& r)
{
return cross(q - p, r - p);
}
void polarSortAround(const Pt& o, vector<pair<Pt, int>>& v, const Pt& u)
{
sort(ALL(v), [&](pair<Pt, int> pp, pair<Pt, int> qq)
{
const Pt& p = pp.F - o;
const Pt& q = qq.F - o;
bool hp = cross(u, p) < 0 || (cross(u, p) == 0 && dot(u, p) < 0);
bool hq = cross(u, q) < 0 || (cross(u, q) == 0 && dot(u, q) < 0);
if (hp != hq)
return hp < hq;
int s = sgn(cross(p, q));
if (s != 0)
return s == 1;
return sq(p) < sq(q);
});
}
bool inDisk(const Pt& a, const Pt& b, const Pt& p)
{
return sgn(dot(a - p, b - p)) <= 0;
}
bool onSegment(const Pt& a, const Pt& b, const Pt& p)
{
return sgn(orient(a, b, p)) == 0 && inDisk(a, b, p);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, s;
cin >> m >> n >> s;
vector<Pt> q(m), p(n);
for (Pt& qi : q)
cin >> qi.x >> qi.y;
for (Pt& pi : p)
cin >> pi.x >> pi.y;
s = mult(s, binpow(100, mod - 2));
vector<pair<Pt, int>> pp(n);
FOR(i, 0, n)
pp[i] = {p[i], 0};
polarSortAround(q[0], pp, {1, 0});
FOR(i, 0, n)
p[i] = pp[i].F;
vector ok(n, VI(n)), cnt(n, VI(n)), cnt2(n, VI(n));
FOR(i, 0, n)
{
FOR(j, 0, n)
{
if (i == j)
continue;
ok[i][j] = 1;
FOR(k, 0, m)
{
ok[i][j] &= !(orient(p[i], p[j], q[k]) <= 0 && !onSegment(p[i], p[j], q[k]));
}
FOR(k, 0, n)
{
if (k != i && k != j && orient(p[i], p[j], p[k]) <= 0 && orient(q[0], p[i], p[k]) >= 0 && orient(q[0], p[j], p[k]) < 0)
cnt[i][j]++;
}
FOR(k, j + 1, n)
{
if (k != i && orient(p[i], p[j], p[k]) <= 0 && orient(q[0], p[i], p[k]) >= 0 && orient(q[0], p[j], p[k]) < 0)
cnt2[i][j]++;
}
}
}
VI pw(n);
pw[0] = 1;
FOR(i, 1, n)
pw[i] = mult(pw[i - 1], sub(1, s));
int ans = 0;
vector<vector<pair<Pt, int>>> p1(n), p2(n);
FOR(j, 0, n)
{
FOR(i, 0, n)
{
LL ori = orient(q[0], p[j], p[i]);
if (i < j && ori <= 0)
p1[j].PB({p[i], i});
if (i > j && ori >= 0)
p2[j].PB({p[i], i});
}
polarSortAround(p[j], p1[j], p[j] - q[0]);
polarSortAround(p[j], p2[j], p[j] - q[0]);
}
FOR(i, 0, n)
{
vector dp(n, VI(n));
FOR(j, i + 1, n)
dp[i][j] = mult(mult(s, pw[cnt[i][j] + i]), ok[i][j]);
FOR(j, i + 1, n)
{
int ptr = 0;
int sum = 0;
for (auto [pk, k] : p2[j])
{
while (ptr < SZ(p1[j]) && orient(p1[j][ptr].F, p[j], pk))
{
updAdd(sum, dp[p1[j][ptr].S][j]);
ptr++;
}
dp[j][k] = mult(sum, mult(mult(s, pw[cnt[j][k]]), ok[j][k]));
if (orient(p[j], p[k], p[i]) > 0)
{
updAdd(ans, mult(dp[j][k], mult(mult(s, pw[cnt2[k][i]]), ok[k][i])));
}
}
}
}
FOR(i, 0, n)
FOR(j, i + 1, n)
{
if (i == j)
continue;
bool good = true;
FOR(k, 0, m)
good &= onSegment(p[i], p[j], q[k]);
int c = 0;
FOR(k, 0, n)
{
if (k != i && k != j && !onSegment(p[i], p[j], p[k]))
{
c++;
}
}
if (good)
{
updAdd(ans, mult(mult(s, s), pw[c]));
}
}
cout << ans << "\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3604kb
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: 3676kb
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: 3524kb
input:
1 2 3 4 5 7 9 -2 -3
output:
184375732
result:
ok single line: '184375732'
Test #4:
score: -100
Wrong Answer
time: 1340ms
memory: 9648kb
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:
851284881
result:
wrong answer 1st lines differ - expected: '963504722', found: '851284881'