QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#814404#9880. Origami Warpucup-team3586#WA 5ms3652kbC++234.2kb2024-12-14 17:16:512024-12-14 17:16:57

Judging History

你现在查看的是最新测评结果

  • [2024-12-14 17:16:57]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:3652kb
  • [2024-12-14 17:16:51]
  • 提交

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]