QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#167034 | #6519. X Equals Y | ucup-team134# | WA | 7ms | 3764kb | C++14 | 1.5kb | 2023-09-06 23:41:49 | 2023-09-06 23:41:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
vector<pair<vector<int>,int>> Cand(int x,int A,int SQ){
vector<pair<vector<int>,int>> ans;
for(int mod=2;mod<=min(SQ,A);mod++){
vector<int> tmp;
int Z=x;
while(Z>0){
tmp.pb(Z%mod);
Z/=mod;
}
ans.pb({tmp,mod});
}
sort(ans.begin(),ans.end());
return ans;
}
bool Solve(int x,int y,int A,int B,int&M1,int&M2){
if(x==y){
M1=2;
M2=2;
return true;
}
int SQ=sqrt(x)+3;
vector<pair<vector<int>,int>> candA=Cand(x,A,SQ);
vector<pair<vector<int>,int>> candB=Cand(y,B,SQ);
for(int i=0,j=0;i<candA.size();i++){
while(j<candB.size() && candB[j].first<candA[i].first){
j++;
}
if(j<candB.size() && candA[i].first==candB[j].first){
M1=candA[i].second;
M2=candB[j].second;
return true;
}
}
for(int a1=1;a1<=SQ;a1++){
int L1=x/(a1+1)+1;
int R1=x/a1;
L1=max(L1,2);
R1=min(R1,A);
int L2=y/(a1+1)+1;
int R2=y/a1;
L2=max(L2,2);
R2=min(R2,B);
int diff=y-x;
if(diff%a1==0){
int gap=diff/a1;
int L3=max(L2,L1+gap);
int R3=min(R2,R1+gap);
if(L3<=R3){
M1=L3-gap;
M2=L3;
return true;
}
}
}
return false;
}
int main(){
int t;
scanf("%i",&t);
while(t--){
int x,y,A,B;
scanf("%i %i %i %i",&x,&y,&A,&B);
int M1,M2;
bool ok;
if(x<=y){
ok=Solve(x,y,A,B,M1,M2);
}else{
ok=Solve(y,x,B,A,M2,M1);
}
if(ok){
printf("YES\n");
printf("%i %i\n",M1,M2);
}else{
printf("NO\n");
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3764kb
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 2 10 YES 4 5 NO YES 6 10
result:
ok correct (6 test cases)
Test #2:
score: -100
Wrong Answer
time: 7ms
memory: 3728kb
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 590 331 YES 14 148 NO YES 244 246 NO YES 77 66 YES 247 42 NO YES 214 286 NO NO NO NO YES 406 136 YES 96 73 YES 12 185 NO YES 103 5 YES 45 37 YES 10 247 NO NO YES 193 17 YES 132 101 NO YES 701 297 NO YES 45 174 NO YES 65 28 YES 57 11 YES 10 39 YES 89 49 YES 6 5 YES 57 10 NO NO NO NO YES 282 87 NO...
result:
wrong answer wrong solution, (722 in base 103) != (36 in base 5) (test case 18)