QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#408450 | #6519. X Equals Y | x17875487211 | WA | 12ms | 4008kb | C++14 | 2.7kb | 2024-05-10 12:31:29 | 2024-05-10 12:31:30 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,x,y,A,B,W[100],cntw;
bool flag,YES;
bool num_is_ok(int num,int lim){
if(num>=2&&num<=lim) return 1;
return 0;
}
bool check_w0(int a,int b,int w1){
if(x-a*w1!=y-b*w1) return 0;
int w0=x-a*w1;
if(w1<0||w1>=min(a,b)) return 0;
if(w0<0||w0>=min(a,b)) return 0;
if(a*w1+w0==x&&b*w1+w0==y&&num_is_ok(a,A)&&num_is_ok(b,B)){
if(flag) swap(a,b);
printf("YES\n%lld %lld\n",a,b),YES=1;
return 1;
}
return 0;
}
bool cal(int w1){
int a=x/w1,b=y/w1;
vector<int> proa,prob;
for(int i=0;i<=10;i++)
proa.push_back(a-i),proa.push_back(a+i),
prob.push_back(b-i),prob.push_back(b+i);
for(auto pa:proa)
for(auto pb:prob)
if(check_w0(pa,pb,w1)) return 1;
return 0;
}
void DI(int Num,int bas){
cntw=0;
while(Num){
W[++cntw]=Num%bas;
Num/=bas;
}
}
int num_base_onb(int di){
int sum=0,mi=1;
int tmp=y;
for(int i=1;i<=cntw;i++){
sum+=W[i]*mi;
if(W[i]>=di) return -1;
mi*=di;
tmp/=di;
}
if(tmp) return -1;
return sum;
}
int bin_seab(){
int l=2,r=B;
while(l<=r){
int mid=(l+r)>>1;
int NUM_BASE_ON=num_base_onb(mid);
if(NUM_BASE_ON==y) return mid;
else if(NUM_BASE_ON<y) l=mid+1;
else r=mid-1;
}
return -1;
}
bool work_on_less_than_sqrta(int a){
DI(x,a);
int b=bin_seab();
if(b!=-1){
if(flag) swap(a,b);
printf("YES\n%lld %lld\n",a,b),YES=1;
return 1;
}
return 0;
}
int num_base_ona(int di){
int sum=0,mi=1;
int tmp=x;
for(int i=1;i<=cntw;i++){
sum+=W[i]*mi;
if(W[i]>=di) return -1;
mi*=di;
tmp/=di;
}
if(tmp) return -1;
return sum;
}
int bin_seaa(){
int l=2,r=B;
while(l<=r){
int mid=(l+r)>>1;
int NUM_BASE_ON=num_base_ona(mid);
if(NUM_BASE_ON==x) return mid;
else if(NUM_BASE_ON<x) l=mid+1;
else r=mid-1;
}
return -1;
}
bool work_on_less_than_sqrtb(int b){
DI(y,b);
int a=bin_seaa();
if(a!=-1){
if(flag) swap(a,b);
printf("YES\n%lld %lld\n",a,b),YES=1;
return 1;
}
return 0;
}
signed main(){
scanf("%lld",&T);
while(T--){
flag=0;
scanf("%lld%lld%lld%lld",&x,&y,&A,&B);
if(x<y) swap(x,y),swap(A,B),flag=1;
YES=0;
for(int i=1;i*i<=(x-y);i++)
if((x-y)%i==0){
if(cal((x-y)/i+1)) break;
if(cal(i+1)) break;
if(cal((x-y)/i)) break;
if(cal(i)) break;
}
if(!YES)
for(int a=2;a<=A&&a*a<=x;a++)
if(work_on_less_than_sqrta(a)) break;
if(!YES)
for(int b=2;b<=B&&b*b<=y;b++)
if(work_on_less_than_sqrtb(b)) break;
if(!YES&&x==y&&A>=x&&B>=y){
if(x==1) printf("YES\n%lld %lld\n",x+1,x+1),YES=1;
else if(num_is_ok(x,A)&&num_is_ok(y,B)) printf("YES\n%lld %lld\n",x,x),YES=1;
}
if(!YES) printf("NO\n");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3988kb
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: 12ms
memory: 4008kb
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 260 55 NO YES 213 249 NO NO NO NO YES 315 135 YES 107 84 YES 15 188 NO NO YES 35 29 YES 12 249 NO NO YES 196 20 YES 151 120 NO YES 498 296 NO YES 67 196 NO YES 66 29 NO NO YES 94 54 YES 6 5 NO NO NO NO NO YES 324 129 NO YES 237 224 YES 211 411 YE...
result:
wrong answer you didn't find a solution but jury did (test case 54)