QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#133714 | #4942. Robust Defense | SolitaryDream# | WA | 1ms | 3496kb | C++20 | 2.7kb | 2023-08-02 13:19:05 | 2023-08-02 13:19:08 |
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];
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 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;
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(!ok)
continue;
int p=1;
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;
}
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 ai<bi;
else
return ai>bi;
});
int ans=0;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
f[j]=(j==i);
for(auto [u,v,p]:E)
{
if(u<i||v<i)
continue;
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;
ans=(ans+f[i]-1)%M;
}
cout<<ans<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3496kb
input:
1 4 50 0 0 -1 0 3 0 0 1 2 -1
output:
623902721
result:
wrong answer 1st lines differ - expected: '686292993', found: '623902721'