QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #369924 | #6510. Best Carry Player 3 | PlentyOfPenalty# | WA | 22ms | 3652kb | C++20 | 1.7kb | 2024-03-28 19:29:53 | 2024-03-28 19:29:53 |
Judging History
answer
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define ll long long
using namespace std;
const int B=60;
int T;
ll tmp,to_0[B+10],to_y[B+10];
ll qx,qy,K;
ll High(ll x){
return 1ll<<(63-__builtin_clzll(x));
}
int Get(ll x){
return 64-__builtin_clzll(x);
}
ll Solve0(ll x){
//cout<<"SOLVE0 "<<x<<"\n";
if(!x)return 0;
ll hb=High(x);
if(K>=x)return 1;
else if(K>=High(x))return min(x,2ll);
//cout<<"TO "<<x-hb<<"\n";
return min(x,Solve0(x-hb)+1+to_0[Get(x)-1]);
}
ll Solve(ll x){
if(x==qy)return 0;
ll hb=High(x);
ll t=(((qy)&((hb<<1)-1))^x);
//cout<<"t="<<t<<"\n";
if(K>=t)return 1;
else if(K>=High(t))return min(x-qy,2ll);
//cout<<"?,Get="<<Get(x)<<"\n";
return min(x-qy,Solve0(x-hb)+1+to_y[Get(x)-1]);
}
int main() {
#ifdef popteam
freopen("J.in", "r", stdin);
#endif
cin.tie(0)->sync_with_stdio(0);
cin>>T;
while(T--){
cin>>qx>>qy>>K;
if(qx<qy)swap(qx,qy);
for(int i=1;(1ll<<i)-1<=qx;++i){
to_0[i]=(1ll<<i)-1;
if(K>=(1ll<<i)-1)to_0[i]=min(to_0[i],1ll);
else if(K>=(1ll<<i-1))to_0[i]=min(to_0[i],2ll);
else to_0[i]=min(to_0[i],(to_0[i-1]<<1)+1);
tmp=(qy&((1ll<<i)-1));
//cout<<"tmp="<<tmp<<"\n";
if(tmp>=(1ll<<i-1))to_y[i]=to_y[i-1];
else{
tmp=((~qy)&((1ll<<i)-1));
to_y[i]=(1ll<<i)-(qy&((1ll<<i)-1))-1;
if(K>=tmp)to_y[i]=min(to_y[i],1ll);
else if(K>=High(tmp))to_y[i]=min(to_y[i],2ll);
else to_y[i]=min(to_y[i],to_0[i-1]+1+to_y[i-1]);
}
//cout<<"IN "<<i<<" to0="<<to_0[i]<<",toy="<<to_y[i]<<"\n";
}
cout<<Solve(qx)<<"\n";
}
}
/*
8
4 5 0
5 8 3
9 2 6
15 28 5
97 47 8
164 275 38
114514 1919 810
0 1152921504606846975 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3652kb
input:
8 4 5 0 5 8 3 9 2 6 15 28 5 97 47 8 164 275 38 114514 1919 810 0 1152921504606846975 1
output:
1 2 3 5 11 6 331 1152921504606846975
result:
ok 8 numbers
Test #2:
score: -100
Wrong Answer
time: 22ms
memory: 3620kb
input:
100000 84 318 6 54 226 7 92 33 0 39 54 5 76 79 7 247 110 0 211 90 0 4 430 3 230 17 1 491 93 5 196 117 7 137 29 2 76 490 6 422 43 7 277 26 4 159 43 1 67 37 5 17 2 5 113 176 7 85 473 0 68 217 7 275 8 7 124 34 1 30 66 0 80 149 3 103 149 6 84 354 1 27 342 7 94 114 1 69 125 1 72 48 7 361 8 7 285 82 1 74 ...
output:
87 45 59 15 1 137 121 213 213 150 21 81 156 95 95 116 12 6 16 388 39 67 90 36 35 17 270 79 20 56 6 89 203 108 26 15 157 98 111 389 174 123 59 289 78 17 21 36 275 191 17 102 60 93 100 11 14 79 44 63 91 60 22 109 11 11 10 67 29 85 207 47 39 83 156 189 107 27 81 247 81 335 33 144 15 50 54 347 233 175 3...
result:
wrong answer 4th numbers differ - expected: '6', found: '15'