QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #814633 | #9880. Origami Warp | ucup-team3586# | RE | 106ms | 3644kb | C++23 | 4.3kb | 2024-12-14 19:01:31 | 2024-12-14 19:01:32 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define int ll
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
ll normalize(ll a,ll b)
{
if(!b) return a;
return (a%b+b)%b;
}
void exgcd(ll a,ll b,ll x,ll y)
{
if(!b)
{
x=1;
y=0;
return ;
}
exgcd(b,a%b,y,x);
y-=(a/b)*x;
}
ll getr(ll a,ll b)
{
ll x,y;
exgcd(a,b,x,y);
return (x%b+b)%b;
}
pair<ll,ll> genM(pair<ll,ll> pr,ll K)
{
ll g=__gcd(pr.second,K);
if(pr.first%g) return mp(-1,-1);
K/=g;
pr.second/=g;
pr.first/=g;
ll need=(K-pr.first%K)%K;
ll ch1=getr(pr.second,K);
longer dest=pr.first+(longer)(need)*ch1*pr.second;
assert(dest%K==0);
dest/=K;
return mp(dest,pr.second);
}
ll chk(ll a,ll b)
{
if(!b) return a==0;
return a%b==0;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int allPassO=1;
int allSlopeOk=1;
int allAlign=1;
ll gcdX=0,gcdY=0;
ll gcdK=0;
for(int i=1;i<=n;i++)
{
ll a,b,c,d;
cin>>a>>b>>c>>d;
if(a*d!=b*c) allPassO=0;
if(a!=c&&b!=d&&abs(a-c)!=abs(b-d)) allSlopeOk=0;
if(a!=c&&b!=d) allAlign=0;
if(a==c) gcdX=__gcd(gcdX,2*abs(a));
if(b==d) gcdY=__gcd(gcdY,2*abs(b));
if(a+b==c+d) gcdK=__gcd(gcdK,abs(a+b));
if(a-b==c-d) gcdK=__gcd(gcdK,abs(a-b));
}
int q;
cin>>q;
for(int i=1;i<=q;i++)
{
ll a,b,c,d;
cin>>a>>b>>c>>d;
if(allPassO&&allSlopeOk)
{
if(allAlign)
cout<<((abs(a)==abs(c)&&abs(b)==abs(d))?"Yes\n":"No\n");
else
cout<<(((abs(a)==abs(c)&&abs(b)==abs(d))||(abs(b)==abs(c)&&abs(a)==abs(d)))?"Yes\n":"No\n");
}
else if(allPassO)
cout<<((a*a+b*b==c*c+d*d)?"Yes\n":"No\n");
else if(allSlopeOk)
{
if(allAlign)
{
int okX=1;
int okY=1;
if(gcdX) okX=((a-c)%gcdX==0||(a+c)%gcdX==0);
else okX=(a-c==0||a+c==0);
if(gcdY) okY=((b-d)%gcdY==0||(b+d)%gcdY==0);
else okY=(b-d==0||b+d==0);
cout<<((okX&&okY)?"Yes\n":"No\n");
}
else
{
int flag=0;
for(int dx=-1;dx<=1;dx+=2)
for(int dy=-1;dy<=1;dy+=2)
{
ll na=normalize(dx*a,gcdX);
ll nb=normalize(dy*b,gcdY);
ll nc=normalize(c,gcdX);
ll nd=normalize(d,gcdY);
ll X=na-nc;
ll Y=nb-nd;
if(!gcdX&&!gcdY)
{
if(X==Y&&chk(X,gcdK)) flag=1;
}
else if(!gcdX)
{
if((X-Y)%gcdY==0&&chk(X,gcdK)) flag=1;
}
else if(!gcdY)
{
if((X-Y)%gcdX==0&&chk(Y,gcdK)) flag=1;
}
else
{
pair<ll,ll> get1=genM(mp(X,gcdX),gcdK);
pair<ll,ll> get2=genM(mp(Y,gcdY),gcdK);
if(~get1.second||~get2.second)
{
ll g=__gcd(get1.second,get2.second);
if((get1.first-get2.first)%g==0) flag=1;
}
}
}
for(int dx=-1;dx<=1;dx+=2)
for(int dy=-1;dy<=1;dy+=2)
{
ll na=normalize(dx*b,gcdX);
ll nb=normalize(dy*a,gcdY);
ll nc=normalize(c,gcdX);
ll nd=normalize(d,gcdY);
ll X=na-nc;
ll Y=nb-nd;
if(!gcdX&&!gcdY)
{
if(X==Y&&chk(X,gcdK)) flag=1;
}
else if(!gcdX)
{
if((X-Y)%gcdY==0&&chk(X,gcdK)) flag=1;
}
else if(!gcdY)
{
if((X-Y)%gcdX==0&&chk(Y,gcdK)) flag=1;
}
else
{
pair<ll,ll> get1=genM(mp(X,gcdX),gcdK);
pair<ll,ll> get2=genM(mp(Y,gcdY),gcdK);
if(~get1.second||~get2.second)
{
ll g=__gcd(get1.second,get2.second);
if((get1.first-get2.first)%g==0) flag=1;
}
}
}
cout<<(flag?"Yes\n":"No\n");
}
}
else
cout<<"Yes\n";
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3644kb
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: 5ms
memory: 3604kb
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: 106ms
memory: 3600kb
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: -100
Runtime Error
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...