QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#133829 | #4942. Robust Defense | SolitaryDream | WA | 656ms | 7004kb | C++20 | 4.8kb | 2023-08-02 14:54:59 | 2023-08-02 14:55:00 |
Judging History
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][6],val[N][6];
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;
assert(a.y!=0);
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)||((v^(a[k]-b[j]))>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;
int mx=0;
for(auto [u,v,p]:E)
{
if(u<i||v<i)
continue;
int r=ty(b[v]-b[u]);
assert(r>=mx);
mx=r;
// 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;
assert(!f[i][1]&&!f[i][2]);
for(int j=1;j<5;j++)
ans=(ans+f[i][j])%M;
}
cout<<ans<<endl;
}
/*
1 8 50
1 1
0 0
0 1
0 2
1 0
1 2
2 0
2 1
2 2
*/
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3540kb
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: 3528kb
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: 3480kb
input:
1 2 3 4 5 7 9 -2 -3
output:
184375732
result:
ok single line: '184375732'
Test #4:
score: 0
Accepted
time: 622ms
memory: 6312kb
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: 656ms
memory: 7004kb
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'