QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#133813#4942. Robust DefenseSolitaryDreamWA 647ms7328kbC++204.6kb2023-08-02 14:21:162023-08-02 14:21:18

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-02 14:21:18]
  • 评测
  • 测评结果:WA
  • 用时:647ms
  • 内存:7328kb
  • [2023-08-02 14:21:16]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define int long long

using tii=tuple<int,int,int>;

const int N=511,M=998244353;

int qpow(int a,int b)
{
    int ret=1;
    while(b)
    {
        if(b&1)
            ret=1ll*ret*a%M;
        b>>=1;
        a=1ll*a*a%M;
    }
    return ret;
}

int n,m,S;

int f[N][5],val[N][5];

struct P{
    int x,y;
}a[N],b[N];

P operator +(const P &a,const P &b)
{
    return {a.x+b.x,a.y+b.y};
}

P operator -(const P &a,const P &b)
{
    return {a.x-b.x,a.y-b.y};
}

int operator *(const P &a,const P &b)
{
    return a.x*b.y-a.y*b.x;
}
int operator ^(const P &a,const P &b)
{
    return a.x*b.x+a.y*b.y;
}
int sgn(const P &a)
{
    if(a.x!=0)
        return a.x>0?-1:1;
    return a.y>0?-1:1;
}

bool operator <(const P &a,const P &b)
{
    if(sgn(a)!=sgn(b))
        return sgn(a)<sgn(b);
    return a*b>0;
}

vector<tii>E;

int ty(const P &a)
{
    if(a.x>0)
        return 1;
    if(a.x<0)
        return 3;
    if(a.y>0)
        return 2;
    if(a.y<0)
        return 4;
    assert(0);
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>S;
    S=S*qpow(100,M-2)%M;
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y;
    for(int i=1;i<=m;i++)
        cin>>b[i].x>>b[i].y;
    sort(b+1,b+m+1,[&](const P &a,const P &b){
        return a.x<b.x||(a.x==b.x&&a.y<b.y);
    });
    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++)
        {
            if(i==j)
                continue;
            P v=b[j]-b[i];
            bool ok=1;
            for(int k=1;k<=n;k++)
            {
                if(v*(a[k]-b[i])<0)
                    ok=0;
                if(v*(a[k]-b[i])==0&&((v^(a[k]-b[i]))<0))
                    ok=0;
            }
            if(!ok)
                continue;
            int p=1;
            if(b[i].x!=b[j].x)
            {
                int lx=b[i].x,rx=b[j].x;
                if(lx<=rx)
                    rx--;
                else
                    rx++,swap(lx,rx);
                for(int k=1;k<=m;k++)
                {
                    if(k==i||k==j)
                        continue;
                    if(b[k].x<lx||b[k].x>rx)
                        continue;
                    if(v*(b[k]-b[i])>=0)
                        continue;
                    p=p*(M+1-S)%M;
                }
            }
            else
            {
                int ly=b[i].y,ry=b[j].y;
                if(ly<=ry)
                    ry--;
                else
                    ry++,swap(ly,ry);
                for(int k=1;k<=m;k++)
                {
                    if(k==i||k==j)
                        continue;
                    if(b[k].y<ly||b[k].y>ry)
                        continue;
                    if(v*(b[k]-b[i])>=0)
                        continue;
                    p=p*(M+1-S)%M;
                }

            }
            E.push_back({i,j,p});
        }
    sort(E.begin(),E.end(), [&](const tii &x,const tii &y) {
        auto [ai,aj,ap]=x;
        auto [bi,bj,bp]=y;
        auto da=b[aj]-b[ai],db=b[bj]-b[bi];
        if(da<db||db<da)
            return da<db;
        if(sgn(da)<0)
            return aj>bj;
        else
            return aj<bj;
    });
    for(int i=1;i<=m;i++)
    {
        for(int j=0;j<5;j++)
            val[i][j]=1;
        for(int j=1;j<=m;j++)
        {
            if(i==j)
                continue;
            if(b[j].x<b[i].x&&b[j].y<=b[i].y)
                val[i][0]=(val[i][0]*(M+1-S))%M;
            if(b[j].x>=b[i].x&&b[j].y<b[i].y)
                val[i][1]=(val[i][1]*(M+1-S))%M;
            if(b[j].x>b[i].x&&b[j].y>=b[i].y)
                val[i][2]=(val[i][2]*(M+1-S))%M;
            if(b[j].x<=b[i].x&&b[j].y>b[i].y)
                val[i][3]=(val[i][3]*(M+1-S))%M;
        }
    }
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        memset(f,0,sizeof(f));
        f[i][0]=1;
        // cerr<<endl;
        for(auto [u,v,p]:E)
        {
            if(u<i||v<i)
                continue;
            int r=ty(b[v]-b[u]);
            // cerr<<r<<endl;
            for(int k=0;k<=r;k++)
            {
                int coe=1;
                for(int t=k;t<r;t++)
                    coe=coe*val[u][t]%M;
                f[v][r]=(f[v][r]+f[u][k]%M*coe%M*p%M*S%M)%M;
            }
            // f[v]=(f[v]+f[u]*p%M*S)%M;
            // f[v]=(f[v]+f[u]%M)%M;
        }
        // cerr<<b[i].x<<" "<<b[i].y<<" "<<f[i]<<endl;
        for(int j=1;j<5;j++)
            ans=(ans+f[i][j])%M;
    }
    cout<<ans<<endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3536kb

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: 1ms
memory: 3692kb

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: 1ms
memory: 3688kb

input:

1 2 3
4 5
7 9
-2 -3

output:

184375732

result:

ok single line: '184375732'

Test #4:

score: 0
Accepted
time: 643ms
memory: 7328kb

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: -100
Wrong Answer
time: 647ms
memory: 6264kb

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:

251419069

result:

wrong answer 1st lines differ - expected: '185827470', found: '251419069'