QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#134561 | #4942. Robust Defense | PhantomThreshold | WA | 3484ms | 6724kb | C++20 | 4.0kb | 2023-08-03 23:44:22 | 2023-08-03 23:44:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long db;
const db eps=0;
int sign(db k){
if (k>eps) return 1;
else if (k<-eps) return -1;
return 0;
}
int cmp(db k1,db k2){
return sign(k1-k2);
}
int inmid(db k1,db k2,db k3){
return sign(k1-k3)*sign(k2-k3)<=0;
}
struct point{
db x,y;
point operator + (const point &k1){return (point){x+k1.x,y+k1.y};}
point operator - (const point &k1){return (point){x-k1.x,y-k1.y};}
point operator * (db k1){return (point){x*k1,y*k1};}
point operator / (db k1){return (point){x/k1,y/k1};}
int operator == (const point &k1){
return cmp(x,k1.x)==0 && cmp(y,k1.y)==0;
}
db abs(){return hypot(x,y);}
db abs2(){return x*x+y*y;}
db dis(point k1){return ((*this)-k1).abs();}
int getP() const{
return sign(y)==-1||(sign(y)==0&&sign(x)==-1);
}
inline void read(){
int a,b;
cin >> a >> b;
x=a;y=b;
}
inline void display(){
cerr << "(" << x << "," << y << ") ";
}
};
int inmid(point k1,point k2,point k3){
return inmid(k1.x,k2.x,k3.x) && inmid(k1.y,k2.y,k3.y);
}
db cross(point k1,point k2){return k1.x*k2.y-k1.y*k2.x;}
db dot(point k1,point k2){return k1.x*k2.x+k1.y*k2.y;}
bool left(point k1,point k2,point q){
return sign(cross(k2-k1,q-k1))>=0;
}
bool on(point k1,point k2,point q){
return sign(cross(k2-k1,q-k1))==0 && inmid(k1,k2,q);
}
int compareangle(point k1,point k2){
return k1.getP()<k2.getP()||(k1.getP()==k2.getP()&&sign(cross(k1,k2))>0);
}
typedef long long ll;
const ll mod=998244353;
inline ll ksm(ll a,ll x){
ll ret=1;
for (;x;x>>=1,a=a*a % mod) if (x&1) ret=ret*a%mod;
return ret;
}
inline ll inv(ll a){
return ksm(a,mod-2);
}
const int maxn=500;
ll n,m;
ll p;
point b[maxn+50];
point a[maxn+50];
bool ok[maxn+50][maxn+50];
ll cost[maxn+50][maxn+50];
int main(){
ios_base::sync_with_stdio(false);
cin >> m >> n >> p;
p=p*inv(100) % mod;
for (int i=1;i<=m;i++) b[i].read();
for (int i=1;i<=n;i++) a[i].read();
sort(a+1,a+n+1,
[&](const point &A,const point &B){
return (A.y==B.y)?(A.x<B.x):(A.y<B.y);
}
);
/*
cerr << "-------------" << endl;
for (int i=1;i<=n;i++) a[i].display();
cerr << endl;
*/
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
if (i==j) continue;
bool flag=1;
for (int k=1;k<=m;k++)
if (!left(a[i],a[j],b[k])){
flag=0;
break;
}
if (!flag) continue;
ok[i][j]=1;
cost[i][j]=1.0;
if (a[j].y<a[i].y){
for (int k=1;k<=n;k++){
if (a[j].y<a[k].y && a[k].y<=a[i].y && left(a[i],a[j],a[k]))
(cost[i][j]*=inv(mod+1-p))%=mod;
}
}
else if (a[j].y>a[i].y){
for (int k=1;k<=n;k++){
if (a[i].y<a[k].y && a[k].y<=a[j].y && !left(a[i],a[j],a[k]))
(cost[i][j]*=mod+1-p)%=mod;
}
}
else if (a[i].x<a[j].x){
for (int k=1;k<=n;k++){
if (on(a[i],a[j],a[k]) && k!=i)
(cost[i][j]*=inv(mod+1-p))%=mod;
}
}
}
}
/*
cerr << "-----------------" << endl;
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
cerr << ok[i][j] << " ";
}
cerr << endl;
}
cerr << endl;
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
cerr << cost[i][j] << " ";
}
cerr << endl;
}
*/
vector<pair<int,int>> preList;
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
if (i==j) continue;
if (!ok[i][j]) continue;
preList.emplace_back(i,j);
}
}
sort(preList.begin(),preList.end(),
[&](const pair<int,int> &A,const pair<int,int> &B){
point va=a[A.second]-a[A.first];
point vb=a[B.second]-a[B.first];
if (sign(cross(va,vb))==0 && sign(dot(va,vb))>0){
if (sign(dot(a[A.second]-a[B.second],va))>0) return 1;
return 0;
}
return compareangle(va,vb);
}
);
ll ans=0;
for (int sel=1;sel<=n;sel++){
vector<ll> dp(n+5);
for (auto [i,j]:preList){
if (i>=sel && j>=sel){
ll src=inv(mod+1-p);
if (i!=sel) src=dp[i];
dp[j]=(dp[j]+src*cost[i][j]%mod*p)%mod;
}
}
ll res=dp[sel];
res=ksm(mod+1-p,n)*res%mod;
ans=(ans+res)%mod;
}
cout << ans << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5620kb
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: 3620kb
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: 1743ms
memory: 6612kb
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: 3163ms
memory: 6724kb
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: 3484ms
memory: 6608kb
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'