QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#814404 | #9880. Origami Warp | ucup-team3586# | WA | 5ms | 3652kb | C++23 | 4.2kb | 2024-12-14 17:16:51 | 2024-12-14 17:16:57 |
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);
}
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&&X%gcdK==0) flag=1;
}
else if(!gcdX)
{
if((X-Y)%gcdY==0&&X%gcdK==0) flag=1;
}
else if(!gcdY)
{
if((X-Y)%gcdX==0&&Y%gcdK==0) 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&&X%gcdK==0) flag=1;
}
else if(!gcdX)
{
if((X-Y)%gcdY==0&&X%gcdK==0) flag=1;
}
else if(!gcdY)
{
if((X-Y)%gcdX==0&&Y%gcdK==0) 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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3612kb
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: -100
Wrong Answer
time: 5ms
memory: 3652kb
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:
100110101001111101001110100111101000001100011100000011111001110111101011100111000101101110010001000001010010011110100010110000101011101111010011010110010000000011000010000110101001101101011101100001011000111101011111100100111001010111101101101100100110001010000010100100010101000001111101110101110010...
result:
wrong output format YES or NO expected, but 100110101001111101001110100111...0110001110110011011110100011110 found [1st token]