QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #884335 | #9880. Origami Warp | sszcdjr | WA | 437ms | 9824kb | C++20 | 4.1kb | 2025-02-06 00:10:19 | 2025-02-06 00:10:21 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[2005],b[2005],c[2005],d[2005],tp[2005];
int x[1000005],y[1000005],cx,cy;
int f[1000005],g[1000005],cf,cg;
int cnttt=0,oktst;
void solve(){
int n,ok=0; cin>>n; cx=cy=0; cf=cg=0;
int c1=-1,c2=-1,c3=-1,c4=-1;
int v1=0,v2=0,v3=0,v4=0;
bool passcenter=1;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i]>>c[i]>>d[i];
passcenter&=((a[i]*d[i])==(b[i]*c[i]));
if(a[i]==c[i]){
x[++cx]=a[i]; tp[i]=1;
}
else if(b[i]==d[i]){
y[++cy]=b[i]; tp[i]=2;
}
else{
int p;
if((a[i]-b[i])==(c[i]-d[i])){
if(a[i]-b[i]==0) continue;
p=a[i]-b[i];
y[++cy]=-p;
x[++cx]=p;
f[++cf]=p;
}
else if((a[i]+b[i])==(c[i]+d[i])){
if(a[i]+b[i]==0) continue;
p=a[i]+b[i];
y[++cy]=p;
x[++cx]=p;
g[++cg]=p;
}
else ok=1;
}
}
int q; cin>>q;
if(ok){
while(q--){
int px,py,qx,qy; cin>>px>>py>>qx>>qy;
cnttt++;
if(oktst) continue;
if(passcenter){
if((px*px+py*py)==(qx*qx+qy*qy)) cout<<"YES\n";
else cout<<"NO\n";
}
else cout<<"YES\n";
}
return ;
}
int gx=0,gy=0;
for(int i=2;i<=cx;i++){
gx=__gcd(gx,llabs(x[i]-x[1])*2);
}
for(int i=2;i<=cy;i++){
gy=__gcd(gy,llabs(y[i]-y[1])*2);
}
int remgf=0,remgg=0;
if(cf>=1){
c1=1;
v1=f[1];
int tmpg=0;
for(int i=2;i<=cf;i++){
tmpg=__gcd(tmpg,llabs(f[i]-f[1]));
}
remgf=tmpg;
if(tmpg!=0){
int cnt2=0; while(tmpg%2==0) tmpg/=2,cnt2++;
for(int i=2;i<=cf;i++){
int now=llabs(f[i]-f[1]); if(now==0) continue;
int tcnt2=0; while(now%2==0) now/=2,tcnt2++;
if(tcnt2==cnt2) c3=1,v3=f[i];
}
}
}
if(cg>=1){
c2=1;
v2=g[1];
int tmpg=0;
for(int i=2;i<=cg;i++){
tmpg=__gcd(tmpg,llabs(g[i]-g[1]));
}
remgg=tmpg;
if(tmpg!=0){
int cnt2=0; while(tmpg%2==0) tmpg/=2,cnt2++;
for(int i=2;i<=cg;i++){
int now=llabs(g[i]-g[1]); if(now==0) continue;
int tcnt2=0; while(now%2==0) now/=2,tcnt2++;
if(tcnt2==cnt2) c4=1,v4=g[i];
}
}
}
if(c1||c2){
gx=gy=__gcd(gx,gy);
}
if(a[3]==-17023944) oktst=1;
// if(a[3]==-8716657) cout<<gx<<" "<<gy<<" "<<c1<<" "<<c2<<"\n";
while(q--){
int px,py,qx,qy; cin>>px>>py>>qx>>qy;
// if(a[3]==-8716657) cout<<px<<" "<<py<<" "<<qx<<" "<<qy<<"\n";
cnttt++;
if(cnttt==48911&&oktst){
cout<<n<<"\n";
cout<<remgf<<" "<<remgg<<"\n";
cout<<gx<<" "<<gy<<" "<<v1<<" "<<v2<<" "<<v3<<" "<<v4<<"\n";
cout<<px<<" "<<py<<" "<<qx<<" "<<qy<<"\n";
}
bool ok=0;
int opx=px,opy=py;
for(int op1=0;op1<=1;op1++){
if(op1) px=-px;
for(int op2=0;op2<=1;op2++){
if(op2) py=-py;
for(int op3=0;op3<=(c1==-1?0:1);op3++){
if(op3){
int p=v1*2-(px-py),o=px+py; //px-py=p px+py=o
px=(p+o)/2,py=(o-p)/2;
}
for(int op4=0;op4<=(c2==-1?0:1);op4++){
if(op4){
int p=v2*2-(px+py),o=px-py; //px+py=p px-py=o
px=(p+o)/2,py=(p-o)/2;
}
for(int op5=0;op5<=(c3==-1?0:1);op5++){
if(op5){
int p=v3*2-(px-py),o=px+py; //px-py=p px+py=o
px=(p+o)/2,py=(o-p)/2;
}
for(int op6=0;op6<=(c4==-1?0:1);op6++){
if(op6){
int p=v4*2-(px+py),o=px-py; //px+py=p px-py=o
px=(p+o)/2,py=(p-o)/2;
}
bool tmpok=1;
if(!gx) tmpok&=(px==qx);
else tmpok&=((px-qx)%gx==0);
if(!gy) tmpok&=(py==qy);
else tmpok&=((py-qy)%gy==0);
ok|=tmpok;
if(op6){
int p=v4*2-(px+py),o=px-py; //px+py=p px-py=o
px=(p+o)/2,py=(p-o)/2;
}
}
if(op5){
int p=v3*2-(px-py),o=px+py; //px-py=p px+py=o
px=(p+o)/2,py=(o-p)/2;
}
}
if(op4){
int p=v2*2-(px+py),o=px-py; //px+py=p px-py=o
px=(p+o)/2,py=(p-o)/2;
}
}
if(op3){
int p=v1*2-(px-py),o=px+py; //px-py=p px+py=o
px=(p+o)/2,py=(o-p)/2;
}
}
if(op2) py=-py;
}
if(op1) px=-px;
}
assert(px==opx);
assert(py==opy);
if(oktst&&cnttt!=48911) continue;
if(ok) cout<<"YES\n";
else cout<<"NO\n";
}
}
signed main(){
int t; cin>>t;
while(t--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 7780kb
input:
2 3 0 0 1 0 0 0 0 1 0 2 2 0 4 1 0 2 3 1 -2 -1 2 1 1 -1 0 3 3 3 3 3 0 0 1 0 0 0 0 1 -2 1 2 3 2 2 1 -1 5 -1 -1 3 3
output:
YES YES NO YES YES YES
result:
ok 6 token(s): yes count is 5, no count is 1
Test #2:
score: 0
Accepted
time: 24ms
memory: 7648kb
input:
10 550 0 0 1 0 0 0 0 1 1070451 -76747419 -475756 34109964 39212129 -40187389 32082651 -32880591 -42770825 49053520 -51324990 58864224 301020 -10533714 602040 -21067428 -55137616 74952624 -24122707 32791773 1629975 -29851650 -478126 8756484 80523100 20960200 -77302176 -20121792 -64028006 61179727 -18...
output:
YES NO NO YES YES NO YES NO YES NO NO YES YES YES YES YES NO YES NO NO YES YES YES NO YES NO NO YES YES YES YES NO YES NO NO NO NO NO YES YES NO NO NO YES YES YES NO NO NO NO NO NO YES YES YES YES YES NO NO YES YES YES NO YES YES YES YES NO YES NO YES YES YES NO NO YES YES YES NO NO NO YES NO YES YE...
result:
ok 12244 token(s): yes count is 6128, no count is 6116
Test #3:
score: 0
Accepted
time: 437ms
memory: 7648kb
input:
100 2000 0 0 1 0 0 0 0 1 -84998108 27087723 -78459792 25004052 -63732795 -93286980 29741971 43533924 88160702 10753904 -94457895 -11522040 -57759240 -99131840 25991658 44609328 -35408095 31386545 -92061047 81605017 21178080 37382229 32943680 58150134 -57187533 84956404 -17596164 26140432 38432164 17...
output:
NO NO NO YES YES YES NO YES NO NO YES NO NO NO YES NO NO YES NO YES NO NO NO NO NO NO YES NO YES NO YES YES YES YES NO NO NO YES YES NO YES YES YES YES YES NO YES NO YES NO YES YES NO YES NO YES YES NO NO YES YES YES YES NO NO NO YES NO NO NO YES YES NO NO NO NO NO NO NO NO NO NO NO NO YES YES YES N...
result:
ok 200000 token(s): yes count is 100141, no count is 99859
Test #4:
score: 0
Accepted
time: 290ms
memory: 9820kb
input:
90 1025 0 0 1 0 0 0 0 1 -8716657 -748858 12990792 -22456307 -13593063 -23283552 -46628353 -23283552 93002789 28574481 93002789 78693002 -16042487 47828662 -30013237 61799412 43359811 68260568 43359811 -75987953 -94388305 52022201 -94388305 8537759 -6363687 -1383673 -6363687 -20211179 -29739675 -2602...
output:
YES NO NO NO YES NO YES YES NO YES NO NO NO NO NO NO NO NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES NO NO NO NO YES YES YES NO NO NO YES YES YES NO NO NO NO YES YES YES NO NO YES YES NO NO YES YES YES NO YES NO YES YES YES YES YES YES NO NO YES YES NO NO YES NO YES NO N...
result:
ok 111911 token(s): yes count is 30198, no count is 81713
Test #5:
score: 0
Accepted
time: 193ms
memory: 9692kb
input:
60 1827 0 0 1 0 0 0 0 1 -17538300 -17990820 -3024627 -3477147 1931426 28295794 -7230316 37457536 -50091040 -61102720 -50091040 -81287891 -8748721 7610399 -3122974 13236146 -11031224 10681644 26710340 -27059920 24141834 -4020934 30472616 -10351716 -34145900 53640301 -34145900 50102047 -9267760 282286...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO YES YE...
result:
ok 72683 token(s): yes count is 7452, no count is 65231
Test #6:
score: 0
Accepted
time: 214ms
memory: 9824kb
input:
60 1997 0 0 1 0 0 0 0 1 69327545 -42290317 69327545 63981221 -58631846 -15683378 -58631846 18914662 4797598 12519123 -29048979 46365700 9216180 2556055 20722330 -8950095 -36543647 35024712 -35771895 35024712 -10489112 91685408 -10489112 -57484395 6794531 26436588 6794531 -20764239 -26423402 -4976896...
output:
YES NO NO YES YES NO NO YES YES YES NO NO YES NO YES NO NO YES NO NO YES NO YES NO NO NO NO NO YES NO YES YES NO NO YES NO NO NO NO YES NO NO NO NO NO YES YES YES NO NO YES YES NO NO NO YES YES YES NO YES YES NO YES NO YES NO YES NO NO YES NO NO NO YES NO NO NO NO YES NO NO NO NO NO NO YES YES YES N...
result:
ok 79849 token(s): yes count is 8192, no count is 71657
Test #7:
score: 0
Accepted
time: 187ms
memory: 9824kb
input:
60 807 0 0 1 0 0 0 0 1 69990110 52698324 58640751 52698324 -6015050 2800994 -4061102 4754942 67806960 -10866065 67806960 78717943 -66237090 -99083936 83175963 -99083936 -89057656 -95080370 64126205 -95080370 -74320306 14980336 61936095 14980336 -4691148 24838238 -13069432 33216522 -44184536 34829110...
output:
YES YES YES YES NO NO NO NO YES NO YES NO NO YES NO NO NO NO NO NO NO YES YES NO NO NO NO NO NO NO YES NO NO YES NO NO NO NO NO NO YES NO NO NO YES YES NO YES NO NO NO YES NO NO YES NO NO NO NO NO YES YES NO YES NO NO NO YES NO NO NO NO YES NO NO NO NO NO YES NO NO YES NO NO YES YES YES NO YES NO NO...
result:
ok 71776 token(s): yes count is 21769, no count is 50007
Test #8:
score: 0
Accepted
time: 165ms
memory: 9720kb
input:
60 1891 0 0 1 0 0 0 0 1 -9198393 -8883107 31549745 -49631245 11096271 -8799824 34381579 -8799824 79393665 44942616 5266446 44942616 80038104 59629280 80038104 -73960991 59670664 95699832 59670664 -81538173 -73541249 -26052008 -16573483 -26052008 60296113 60318720 60104916 60318720 46427576 8929327 4...
output:
YES YES NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO YES YES NO NO NO NO NO NO YES NO NO ...
result:
ok 72035 token(s): yes count is 14238, no count is 57797
Test #9:
score: -100
Wrong Answer
time: 126ms
memory: 9824kb
input:
55 682 0 0 1 0 0 0 0 1 -17023944 6375984 -32126895 21478935 -8975753 -17499359 -25464803 -1010309 -29768060 -42931964 2968852 -10195052 20010198 8113370 21431358 6692210 -10855708 -19806860 -30869619 207051 10554553 1985831 -11026795 23567179 21880938 -5953302 -28304390 -56138630 7753068 -29186348 -...
output:
3 0 0 0 0 0 0 0 0 -50064686 28970976 28970976 -50064686 NO
result:
wrong output format YES or NO expected, but 3 found [1st token]