QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#510256#4942. Robust Defenseideograph_advantageWA 3094ms6896kbC++207.1kb2024-08-09 00:41:592024-08-09 00:42:00

Judging History

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

  • [2024-08-09 00:42:00]
  • 评测
  • 测评结果:WA
  • 用时:3094ms
  • 内存:6896kb
  • [2024-08-09 00:41:59]
  • 提交

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'