QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#133838 | #4942. Robust Defense | SolitaryDream | AC ✓ | 749ms | 7860kb | C++20 | 4.9kb | 2023-08-02 15:12:20 | 2023-08-02 15:12:24 |
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]);
ans=(ans+f[i][4])%M;
ans=(ans+f[i][3]*val[i][3])%M;
// cerr<<i<<" "<<ans*qpow(2,m)%M<<endl;
}
cout<<ans<<endl;
}
/*
1 8 50
1 1
0 0
0 1
0 2
1 0
1 2
2 0
2 1
2 2
1 4 50
1 1
0 0
0 2
2 0
2 2
*/
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: 0ms
memory: 3484kb
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: 3540kb
input:
1 2 3 4 5 7 9 -2 -3
output:
184375732
result:
ok single line: '184375732'
Test #4:
score: 0
Accepted
time: 619ms
memory: 6276kb
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: 662ms
memory: 7064kb
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: 0
Accepted
time: 650ms
memory: 6296kb
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:
682068131
result:
ok single line: '682068131'
Test #7:
score: 0
Accepted
time: 214ms
memory: 4832kb
input:
2 500 46 -403094522 914929192 320656252 -843577464 586600018 642224251 -794800672 841965120 808257851 -869708616 -876762250 -844243852 412194069 -338347112 -173741653 -792568559 399831618 -345749797 910054388 -498157999 -565130894 -50068333 860559597 -840842373 311687063 -961147442 41929748 -5115264...
output:
195721515
result:
ok single line: '195721515'
Test #8:
score: 0
Accepted
time: 331ms
memory: 6772kb
input:
2 500 58 13 22 19 14 13 18 4 9 16 14 16 20 20 3 14 16 8 10 6 7 11 12 12 4 13 21 18 7 15 19 18 19 18 16 1 9 19 5 5 20 10 1 22 11 0 13 10 0 3 17 20 16 4 15 1 5 21 14 12 15 12 10 22 2 10 7 11 22 8 20 3 8 11 14 4 12 9 17 17 6 7 9 6 20 7 13 13 12 20 11 10 16 21 13 19 15 9 3 6 13 18 1 11 10 22 15 11 11 3 ...
output:
46278926
result:
ok single line: '46278926'
Test #9:
score: 0
Accepted
time: 297ms
memory: 4836kb
input:
3 500 19 477551214 116061473 -309499376 243357246 255365680 -699209646 -750786271 86605756 -807598693 -928286047 330005865 -456468606 -449611339 556234005 686992701 -749656969 -140629011 -481764646 -566102582 679115661 776165074 567358130 899797045 303332290 -546338744 -83179721 -653692787 -26889721...
output:
876479951
result:
ok single line: '876479951'
Test #10:
score: 0
Accepted
time: 235ms
memory: 4940kb
input:
3 500 55 1 1 18 4 8 15 3 17 22 19 4 5 15 16 6 3 3 19 3 21 3 7 5 6 15 0 2 15 11 14 6 9 10 3 1 18 9 12 0 6 21 20 0 18 21 8 13 11 13 14 2 12 2 5 21 2 0 16 8 5 9 16 2 16 16 11 22 16 18 13 22 13 4 22 1 11 19 17 13 0 3 6 10 18 2 3 8 0 20 9 5 19 6 21 0 19 21 13 14 10 19 5 21 18 0 8 7 17 2 4 22 14 19 9 18 1...
output:
867641008
result:
ok single line: '867641008'
Test #11:
score: 0
Accepted
time: 317ms
memory: 4912kb
input:
4 500 7 -476636592 -854537496 -908406853 932381623 -707068754 -890003066 58385260 -291357753 -709549006 -724582725 371070418 -158976412 684589595 265105012 -473323100 -691413669 967970807 -711091272 -72050470 197751371 637463713 791283940 -93706748 297610630 -579642099 206973956 33573278 165926209 1...
output:
203258992
result:
ok single line: '203258992'
Test #12:
score: 0
Accepted
time: 275ms
memory: 4824kb
input:
4 500 14 4 11 10 16 10 19 15 10 14 11 5 17 4 7 12 16 5 2 18 22 13 21 19 0 18 16 5 6 19 17 9 0 13 13 3 10 20 15 14 0 15 11 8 12 22 9 6 7 20 22 15 16 0 11 11 2 20 18 1 18 2 2 1 9 16 12 16 4 5 3 6 20 0 12 14 17 7 17 3 19 4 9 17 0 10 2 19 13 20 11 16 20 13 20 20 13 4 3 12 4 6 12 12 18 6 9 22 20 1 15 3 1...
output:
234632203
result:
ok single line: '234632203'
Test #13:
score: 0
Accepted
time: 237ms
memory: 4812kb
input:
22 500 85 13 15 13 25 13 16 13 7 13 26 13 20 13 21 13 1 13 3 13 11 13 14 13 18 13 8 13 17 13 9 13 13 13 12 13 6 13 23 13 10 13 19 13 2 24 3 10 15 12 21 18 4 24 26 19 26 22 18 1 25 5 21 25 15 18 16 17 2 12 14 14 11 5 10 27 5 8 22 7 14 11 27 6 0 19 4 17 17 6 6 9 2 3 22 24 21 22 22 3 10 1 26 27 12 2 17...
output:
887019918
result:
ok single line: '887019918'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3540kb
input:
1 3 1 0 0 1 0 2 0 -1 0
output:
976898894
result:
ok single line: '976898894'
Test #15:
score: 0
Accepted
time: 265ms
memory: 6332kb
input:
5 500 82 5 17 6 17 7 17 8 17 18 17 7 21 8 7 22 8 20 16 19 9 18 20 0 11 10 20 16 4 15 9 11 2 15 20 1 13 20 15 14 16 0 7 21 6 14 12 11 0 16 12 13 11 5 14 17 17 19 21 19 6 22 20 16 1 11 13 7 4 21 8 1 20 14 7 4 20 8 10 16 14 10 7 7 6 21 3 0 14 19 19 1 9 8 1 19 5 6 18 15 16 8 2 11 7 16 8 0 1 15 8 0 13 15...
output:
725728375
result:
ok single line: '725728375'
Test #16:
score: 0
Accepted
time: 198ms
memory: 4828kb
input:
7 500 56 33 39 24 12 22 6 30 30 29 27 21 3 23 9 2 22 30 2 0 35 33 37 26 14 32 33 42 40 0 23 30 18 20 38 36 37 38 36 23 39 3 6 6 13 38 14 28 20 23 31 38 21 6 31 1 7 40 37 21 0 26 12 22 21 16 17 32 34 13 4 11 28 37 33 33 28 1 11 16 1 2 34 4 9 15 24 23 7 20 3 14 38 11 7 40 41 29 33 34 15 1 24 38 41 23 ...
output:
312153189
result:
ok single line: '312153189'
Test #17:
score: 0
Accepted
time: 190ms
memory: 3840kb
input:
500 500 53 839260745 344916325 839260745 235500481 839260745 671386212 839260745 -280235618 839260745 -86590303 839260745 337510956 839260745 -182522139 839260745 -597396479 839260745 822607915 839260745 660094661 839260745 926197409 839260745 -533044257 839260745 235274122 839260745 -168053127 8392...
output:
792585131
result:
ok single line: '792585131'
Test #18:
score: 0
Accepted
time: 261ms
memory: 4840kb
input:
125 500 64 -141451513 335567220 -569848697 335567220 -388992260 335567220 -992701005 335567220 -250590710 335567220 -91355773 335567220 -489615703 335567220 7554245 335567220 -226231803 335567220 -839346275 335567220 -902123132 335567220 -588045845 335567220 -383826078 335567220 -575357505 335567220...
output:
270132479
result:
ok single line: '270132479'
Test #19:
score: 0
Accepted
time: 210ms
memory: 3552kb
input:
500 500 42 -79195047 -961485472 335635421 -865755364 466131514 -835640881 42257505 -933457960 362168850 -859632265 545938293 -817223932 383691468 -854665507 988199242 -715163713 351944051 -861991834 122048840 -915044575 39515259 -934090786 201812966 -896637469 -139851292 -975483067 -160417656 -98022...
output:
277408113
result:
ok single line: '277408113'
Test #20:
score: 0
Accepted
time: 162ms
memory: 3676kb
input:
500 500 92 596423239 295663345 126269009 295663345 392209845 295663345 946086763 295663345 -587440099 295663345 609944971 295663345 541149279 295663345 76239547 295663345 355877801 295663345 -909476583 295663345 -684641161 295663345 911167557 295663345 -751247183 295663345 386126075 295663345 -97494...
output:
342415679
result:
ok single line: '342415679'
Test #21:
score: 0
Accepted
time: 267ms
memory: 4812kb
input:
23 500 19 -168796364 -738629922 840538535 -391018528 -851903656 -973889674 749805159 -422266784 -480772972 -846073570 297233476 -578130882 132006547 -635034456 635226052 -461727426 -817314244 -961977202 199283894 -611864374 -381419119 -811856452 -377811016 -810613834 611534858 -469886590 -64692178 -...
output:
867381472
result:
ok single line: '867381472'
Test #22:
score: 0
Accepted
time: 254ms
memory: 4836kb
input:
4 500 5 446114147 62330869 381448696 114714436 834106853 -251970533 122786892 324248704 187279696 124044421 578890722 807472082 -71209461 481399405 467965318 110897752 262440310 189995290 -538945687 508863404 -617030073 -275412300 -197870727 117814473 439229417 74931589 242643495 717650048 30809842 ...
output:
105841299
result:
ok single line: '105841299'
Test #23:
score: 0
Accepted
time: 719ms
memory: 7300kb
input:
500 500 18 527 1274 -1072 -960 -1065 -967 1421 58 857 1118 1378 -412 -1292 -631 1080 -1013 -815 -1156 357 -1344 -652 1272 1177 -898 1125 -966 1412 -238 198 1353 -216 1375 -1388 375 -954 1107 582 1255 -717 -1209 -399 -1324 -516 1318 -1383 -340 213 -1367 377 -1340 -1413 227 -1149 931 1014 987 -530 131...
output:
826686575
result:
ok single line: '826686575'
Test #24:
score: 0
Accepted
time: 493ms
memory: 6260kb
input:
500 500 61 1348 -1383 1765 567 -1308 1378 -1122 -1626 -1040 1605 -1486 1166 -545 -1865 1810 368 1114 1675 1786 481 -1010 -1687 -623 1796 1847 130 -1858 -63 -1856 -33 711 -1777 956 -1670 1830 263 -1326 -1476 1840 -276 -1520 1116 1733 -712 508 -1837 1481 1287 1806 -469 -1385 1294 -1718 -848 -724 -1810...
output:
101380411
result:
ok single line: '101380411'
Test #25:
score: 0
Accepted
time: 1ms
memory: 3428kb
input:
1 3 99 0 0 0 1 0 -1 0 2
output:
987945467
result:
ok single line: '987945467'
Test #26:
score: 0
Accepted
time: 645ms
memory: 6276kb
input:
1 500 84 0 0 -528626526 850274457 231477980 980386745 -928052116 -435062741 120978206 -985648195 450564112 -899544475 -136854600 984213577 816504922 624013015 979145282 -145180217 -762063278 -750298027 -650606796 764170737 -470267338 880410759 -251659560 961730939 902130288 445108619 262092636 97512...
output:
830242511
result:
ok single line: '830242511'
Test #27:
score: 0
Accepted
time: 749ms
memory: 7048kb
input:
500 500 32 132 1739 1215 1218 -1102 1519 1620 683 1110 -1433 638 -1684 -1751 311 -884 1625 -1154 1486 1157 -1390 1386 1056 -65 -1752 1255 -1292 1766 84 -268 -1724 -816 -1572 1517 -917 401 1676 587 -1698 1669 -534 -1596 -772 -1619 -712 662 1570 1274 1170 -1741 -214 1692 482 365 -1741 617 -1690 -474 -...
output:
696038389
result:
ok single line: '696038389'
Test #28:
score: 0
Accepted
time: 103ms
memory: 3568kb
input:
500 500 65 432253349 -481926159 -376816475 112183262 781308082 936712612 247234697 -757378669 501254368 -910074338 -99238771 435023770 700216182 446258009 -313205674 312197967 481562691 -672726561 788848861 -896921357 259254316 513368703 -4675860 -322240377 -307547478 988464243 -375031315 100008950 ...
output:
826440261
result:
ok single line: '826440261'
Test #29:
score: 0
Accepted
time: 96ms
memory: 3580kb
input:
451 500 16 396671259 -386006440 668340741 827795851 -6858858 -599240263 208373337 502052889 -254230496 -594403716 -837643412 -239991778 740834719 -674070836 -279976628 250975793 -11467466 -917838738 -122208252 -432480867 564533642 85955733 332571090 763072513 177473146 -425386399 -395577764 -3887236...
output:
294803840
result:
ok single line: '294803840'
Test #30:
score: 0
Accepted
time: 626ms
memory: 7240kb
input:
3 500 97 328578360 500000001 264781007 500000000 328578359 500000001 989966597 875321135 630239494 543805882 994085850 804466456 500000000 1000000000 7343998 471796011 944228688 383988188 290214042 443683005 10983492 531385492 616623513 546601837 501996981 390131306 740558923 802436874 752293819 813...
output:
586259231
result:
ok single line: '586259231'
Test #31:
score: 0
Accepted
time: 562ms
memory: 7860kb
input:
3 500 33 587599306 499999999 471788361 500000000 587599305 499999999 210313053 314632869 647883985 1580333 617255658 301702573 735308426 471987789 315987477 579447631 593610495 385548804 682729682 549093584 353748846 805657954 658513175 151847362 362633781 910695628 937199763 672717111 985460116 421...
output:
10201997
result:
ok single line: '10201997'
Test #32:
score: 0
Accepted
time: 1ms
memory: 3536kb
input:
500 2 2 -692151163 -692151163 -454664468 -454664468 -144826769 -144826769 214233013 214233013 135793196 135793196 -156501079 -156501079 -414475065 -414475065 -651049086 -651049086 700216564 700216564 170127714 170127714 587556453 587556453 806334675 806334675 856030266 856030266 228901602 228901602 ...
output:
192860809
result:
ok single line: '192860809'
Test #33:
score: 0
Accepted
time: 1ms
memory: 3704kb
input:
500 3 98 -512340885 -512340885 -997029267 -997029267 -690147962 -690147962 451031393 451031393 660079977 660079977 -682847635 -682847635 -770210362 -770210362 -670642835 -670642835 -199677781 -199677781 812980776 812980776 30263600 30263600 79584620 79584620 533146990 533146990 723768241 723768241 8...
output:
871666970
result:
ok single line: '871666970'
Test #34:
score: 0
Accepted
time: 1ms
memory: 3536kb
input:
500 4 69 -147393506 -147393506 797423132 797423132 -651139712 1000000000 -525783468 1000000000 -1000000000 -523636520 588348702 1000000000 996032759 1000000000 708229878 1000000000 -839163871 1000000000 -1000000000 498930317 383458738 383458738 -270192638 1000000000 -1000000000 19807507 768110798 10...
output:
975631124
result:
ok single line: '975631124'
Test #35:
score: 0
Accepted
time: 99ms
memory: 3728kb
input:
500 500 81 206580046 134047298 -427778766 466093599 -22036603 -379577430 -424239741 254556669 784782806 224166348 884671106 -983006421 -351956966 -336961309 -354193877 -749463345 -324116521 -448498195 -213324401 495343715 -902406237 482217448 -335066351 676938165 -545768594 -621327963 269635892 -965...
output:
365281330
result:
ok single line: '365281330'
Test #36:
score: 0
Accepted
time: 109ms
memory: 3564kb
input:
500 500 68 30 7 14 22 25 12 31 22 5 13 14 17 17 2 10 13 2 30 19 6 3 20 5 12 14 15 11 20 5 25 18 2 26 27 23 17 20 3 15 23 6 20 16 3 14 6 16 1 30 25 23 7 17 17 15 19 19 24 14 14 13 22 15 2 25 23 18 13 17 18 30 19 11 9 12 17 3 31 22 4 18 20 22 8 22 28 14 26 31 17 15 11 7 4 24 18 24 16 26 13 30 30 28 8 ...
output:
214004082
result:
ok single line: '214004082'
Test #37:
score: 0
Accepted
time: 447ms
memory: 4816kb
input:
500 500 2 430129881 238289397 -914438860 479901040 -408661489 441351738 -780641660 -339519020 -484668146 667719151 -407348873 -402482170 -647219856 148970953 327834986 138603178 -130700654 -147204101 -484955130 802278630 -131282996 841226167 223799381 -384703697 -434819306 829705576 -597846325 -1690...
output:
48153586
result:
ok single line: '48153586'