QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#358211#6519. X Equals YDoqeWA 2ms7756kbC++201.8kb2024-03-19 18:11:552024-03-19 18:11:56

Judging History

This is the latest submission verdict.

  • [2024-03-19 18:11:56]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 7756kb
  • [2024-03-19 18:11:55]
  • Submitted

answer

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
mt19937 rnd(1375413);
unsigned msk[32];
unsigned F(int x,int y)
{
	unsigned C=0,A=0;
	while(x)A+=msk[C++]*(x%y),x/=y;
	return A;
}
string tr(int x,int y)
{
	string A;
	while(x)A+=to_string(x%y),x/=y;
	return A;
}
struct node
{
	int l,r,v;
}K[101000];
int t;int X,Y;
void YES(int x,int y)
{
	cout<<"YES\n"<<x<<" "<<y<<"\n";
//	cerr<<tr(X,x)<<"   "<<tr(Y,y)<<endl;
}
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int rd() {
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
	return x*f;
}
void solve()
{
gp_hash_table<unsigned,int>S;
	int x=rd(),y=rd(),A=rd(),B=rd();
	X=x,Y=y;
	if(x==1||y==1)
	{
		if(x==y)return YES(2,2);
		if(x!=y){cout<<"NO\n";return;}
	}
	if(A>=x&&B>=y)return YES(x,y);
	A=min(A,x),B=min(B,y);
	int lA=min(A,(int)sqrt(x)),lB=min(B,(int)sqrt(y));
	S.clear();
	for(int i=2;i<=lA&&i<=1000;++i)S[F(x,i)]=i;unsigned w1;
	for(int i=2;i<=lB&&i<=1000;++i)if(S.find(w1=F(y,i))!=S.end())return YES(S[w1],i);
	t=0;
	for(int l=2*lA+1,r,w;l<=A;l=r+1)
	{
		r=x/(w=x/l);
		K[++t]={l,min(A,r),w};
	}
	int p=1;
	for(int l=2*lB+1,r,w;l<=B;l=r+1)
	{
		r=y/(w=y/l);r=min(B,r);
		while(p<=t&&K[p].v>w)++p;
		if(p<=t&&K[p].v==w)
		{
			if(x%w!=y%w)continue;
			int xl=x-K[p].r*w,xr=x-K[p].l*w;
			int yl=y-     r*w,yr=y-     l*w;
			if(max(xl,yl)<=min(xr,yr))
			{
				int z=max(xl,yl);
				YES((x-z)/w,(y-z)/w);
				return;
			}
		}
	}
	cout<<"NO\n";
}
int main()
{
	cin.tie(0)->sync_with_stdio(0);
	for(int i=0;i<31;++i)msk[i]=rnd();
	int T=rd();
	while(T--)solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 7756kb

input:

6
1 1 1000 1000
1 2 1000 1000
3 11 1000 1000
157 291 5 6
157 291 3 6
10126 114514 789 12345

output:

YES
2 2
NO
YES
3 11
YES
4 5
NO
YES
6 10

result:

ok correct (6 test cases)

Test #2:

score: -100
Wrong Answer
time: 2ms
memory: 5944kb

input:

1000
920 661 756 534
52 454 31 218
980 77 812 6
729 733 289 660
161 643 21 475
602 525 329 274
782 167 279 113
875 100 388 16
426 498 341 417
433 751 312 39
91 50 47 39
941 388 247 46
725 808 148 486
945 405 700 145
647 509 152 445
45 564 16 468
843 40 530 3
722 36 323 22
568 472 443 41
38 749 25 42...

output:

YES
131 94
YES
17 151
NO
YES
182 183
NO
YES
54 47
YES
25 10
NO
YES
47 55
NO
NO
NO
NO
YES
105 45
YES
107 84
YES
15 188
NO
NO
NO
NO
NO
NO
YES
16 5
YES
151 120
NO
YES
249 148
NO
YES
44 130
NO
NO
NO
NO
YES
75 43
YES
6 5
NO
NO
NO
NO
NO
YES
108 43
NO
YES
237 224
YES
17 25
YES
288 45
NO
NO
NO
NO
NO
NO
YES
...

result:

wrong answer you didn't find a solution but jury did (test case 19)