QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#139793#6519. X Equals YMaxBlazeResFireWA 1ms3716kbC++142.8kb2023-08-14 16:47:292023-08-14 16:47:32

Judging History

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

  • [2023-08-14 16:47:32]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3716kb
  • [2023-08-14 16:47:29]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define int long long

int X,Y,A,B,swa;

inline bool solve2(){
	vector<int> factor;
	for( int p = 1 ; p * p < X ; p ++ )
		if( ( X - Y ) % p == 0 ) factor.emplace_back( p );//cerr << p << "\n";
	for( int p : factor ){
		int L = max( X / ( p + 1 ) , ( X * p + X - Y ) / ( p * p + p ) );
		L = max( L , max( 2 + ( X - Y ) / p , ( p * p + X - Y ) / p ) );
		L = max( L , p ); L ++;
		int R = min( min( A , X ) , min( B + ( X - Y ) / p , Y + ( X - Y ) / p ) );
		R = min( R , X / p );
		//cerr << p << " " << L << " " << R << "\n";
		if( L <= R ){
			int a = ( L + R ) >> 1,b = ( Y - X ) / p + a;
			if( swa ) swap( a , b );
			//cerr << "there" << "\n";
			printf("YES\n%lld %lld\n",a,b);
			return 1;
		}
	}
	return 0;
}

struct sequence{
	int Len,Rtag;
	vector<int> seq;
	sequence( int p = 0 ){ Rtag = p,seq = vector<int>(1),Len = 0; }
	inline void prt(){
		cerr << Len << " " << Rtag << "\n";
		for( int ele : seq ) cerr << ele << " "; cerr << "\n";
	}
};

inline bool cmp( sequence A , sequence B ){
	if( A.Len != B.Len ) return A.Len < B.Len;
	for( int i = 1 ; i <= A.Len ; i ++ )
		if( A.seq[i] != B.seq[i] ) return A.seq[i] < B.seq[i];
	return 0;
}

inline bool judge( sequence A , sequence B ){
	if( A.Len != B.Len ) return 0;
	for( int i = 1 ; i <= A.Len ; i ++ )
		if( A.seq[i] != B.seq[i] ) return 0;
	return 1;
}

vector<sequence> Sa,Sb;

inline bool solve3(){
	int lenA = 0,lenB = 0;
	Sa.clear(),Sb.clear();
	Sa.emplace_back( sequence() ),Sb.emplace_back( sequence() );
	for( int a = 2 ; a <= A && a * a <= X ; a ++ ){
		Sa.emplace_back( sequence( a ) ),lenA ++;
		int tmp = X;
		while( tmp ) Sa[lenA].Len ++,Sa[lenA].seq.emplace_back( tmp % a ),tmp /= a;
	}
	for( int b = 2 ; b <= B && b * b <= Y ; b ++ ){
		Sb.emplace_back( sequence( b ) ),lenB ++;
		int tmp = Y;
		while( tmp ) Sb[lenB].Len ++,Sb[lenB].seq.emplace_back( tmp % b ),tmp /= b;
	}
	//sort( Sa.begin() , Sa.end() , cmp );
	//sort( Sb.begin() , Sb.end() , cmp );
	//for( sequence A : Sa ) A.prt();
	//for( sequence B : Sb ) B.prt();
	int ptb = 1;
	for( int pta = 1 ; pta <= lenA ; pta ++ ){
		while( ptb <= lenB && cmp( Sb[ptb] , Sa[pta] ) ) ptb ++;
		if( ptb > lenB ) return 0;
		if( judge( Sa[pta] , Sb[ptb] ) ){
			int Ansa = Sa[pta].Rtag,Ansb = Sb[ptb].Rtag;
			if( swa ) swap( Ansa , Ansb );
			printf("YES\n%lld %lld\n",Ansa,Ansb);
			return 1;
		}
	}
	return 0;
}

inline void solve(){
	scanf("%lld%lld%lld%lld",&X,&Y,&A,&B);
	if( X == Y ){ printf("YES\n2 2\n"); return; }
	if( X < Y ) swap( X , Y ),swap( A , B ),swa = 1; else swa = 0;
	if( !solve2() ){ if( !solve3() ) printf("NO\n"); }
}

signed main(){
	int testcase; scanf("%lld",&testcase);
	while( testcase -- ) solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3716kb

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
NO
NO
YES
784 9483

result:

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