QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#358210#6519. X Equals YDoqeWA 49ms8016kbC++201.8kb2024-03-19 18:11:322024-03-19 18:11:32

Judging History

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

  • [2024-03-19 18:11:32]
  • 评测
  • 测评结果:WA
  • 用时:49ms
  • 内存:8016kb
  • [2024-03-19 18:11:32]
  • 提交

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<=500;++i)S[F(x,i)]=i;unsigned w1;
	for(int i=2;i<=lB&&i<=500;++i)if(S.find(w1=F(y,i))!=S.end())return YES(S[w1],i);
	t=0;
	for(int l=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=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: 1ms
memory: 7692kb

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: 0
Accepted
time: 2ms
memory: 7820kb

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
8 75
NO
YES
182 183
NO
YES
54 47
YES
25 10
NO
YES
23 27
NO
NO
NO
NO
YES
52 22
YES
107 84
YES
15 188
NO
NO
YES
35 29
YES
12 249
NO
NO
YES
16 5
YES
151 120
NO
YES
249 148
NO
YES
22 65
NO
YES
66 29
NO
NO
YES
37 21
YES
6 5
NO
NO
NO
NO
NO
YES
43 17
NO
YES
38 36
YES
17 25
YES
96 15
NO
NO
NO...

result:

ok correct (1000 test cases)

Test #3:

score: 0
Accepted
time: 36ms
memory: 5748kb

input:

1000
312788 308299 292039 230765
263760 329714 198045 86472
945524 951268 792172 748100
922790 262573 363596 34883
755556 714487 234743 610394
413603 489527 114329 351936
409240 356171 378350 234973
300813 97383 263307 49846
579258 900270 84403 704902
563965 876076 387516 770189
36896 156893 23161 1...

output:

YES
4668 4601
YES
2691 3364
YES
1316 1324
NO
YES
107936 102069
YES
806 954
YES
288042 234973
YES
10027 3246
YES
801 1245
YES
62662 97341
YES
139 338
YES
27151 26694
YES
483 960
YES
1106 587
YES
894 865
YES
1381 9024
NO
YES
10657 4166
YES
12558 8399
YES
581 2360
YES
1145 1102
YES
1768 1715
YES
68 138...

result:

ok correct (1000 test cases)

Test #4:

score: -100
Wrong Answer
time: 49ms
memory: 8016kb

input:

1000
981241785 906230829 601363803 626653490
197057696 698550046 128696358 449956015
182548925 796382933 101642956 339324198
816288818 177783961 308532802 32376477
628394197 777548138 355072973 757299936
599075146 752655475 473746059 323396924
261214299 95047810 181049121 60329182
7484303 329571035 ...

output:

YES
35005 32329
YES
15698 55648
YES
54720 238723
YES
146893 31992
YES
15326687 18964588
YES
26084 32771
NO
YES
4910 216253
YES
1796495 1768498
YES
29675 32561
NO
YES
8181622 7836311
YES
52569 390568
YES
43467 45196
YES
66325 101378
YES
3087161 541984
YES
3156893 762966
NO
YES
52726 115823
YES
696995...

result:

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