QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #123268 | #6510. Best Carry Player 3 | Si23 | WA | 13ms | 1744kb | C++14 | 2.8kb | 2023-07-11 23:19:55 | 2023-07-11 23:19:59 |
Judging History
answer
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
#define ones(d) ((1 << (d)) - 1)
ll X, Y, K;
int s[100];
int digits(ll k){
int res = 0;
while(k){
res++;
k >>= 1ll;
}
return res;
}
int main(){
int T;
scanf("%d\n", &T);
while(T--){
scanf("%lld%lld%lld", &X, &Y, &K);
if(X == Y){
printf("0");
continue;
}
if(K <= 1){
printf("%lld\n", llabs(X - Y));
continue;
}
int steps = 0;
if(X > Y) swap(X, Y);
int d = digits(K + 1) - 1;
int y = digits(Y);
// printf("%d, %d\n", y, d);
if(y == d){
printf("1\n");
continue;
}
if(y == d + 1){
if((X ^ Y) <= K)
printf("1\n");
else if((X & ones(d)) == ones(d)){
if((Y & ones(d)) == 0)
printf("1\n");
else
printf("2\n");
}
else{
if((Y & ones(d)) == 0)
printf("2\n");
else
printf("3\n");
}
continue;
}
if((X & ones(d+1)) != ones(d+1)){
if(((X & ones(d+1)) ^ ones(d+1)) <= K)
steps++;
else if((X & ones(d)) == ones(d)){
if((Y & ones(d)) == 0)
steps++;
else
steps += 2;
}
else{
if((Y & ones(d)) == 0)
steps += 2;
else
steps += 3;
}
}
if(K & (1 << d)){
s[d] = 0;
s[d + 1] = 2;
}
else{
s[d] = 1;
s[d + 1] = 3;
}
for(int i = d + 2; i < y; i++)
s[i] = (s[i - 1] << 1) + 1;
// for(int i = d; i < y; i++)
// printf("s[%d] = %d\n", i, s[i]);
for(int i = d + 2; i < y; i++){
if(X & (1 << (i - 1))) continue;
else steps += s[i - 1] + 1;
}
steps++;
// printf("cur = %d\n", steps);
for(int i = y - 1; i > d + 1; i--){
if((Y & (1 << (i - 1))) == 0) continue;
steps += s[i - 1] + 1;
}
if((Y & ones(d + 1)) != 0){
if((Y & ones(d + 1)) <= K)
steps++;
else{
if(K & (1 << d))
steps += 2;
else if ((Y & ones(d)) == 0)
steps += 2;
else
steps += 3;
}
}
printf("%d\n", steps);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 1744kb
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: 13ms
memory: 1616kb
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 18 17 137 121 213 213 150 21 81 156 95 96 116 12 6 15 388 39 67 90 36 35 17 270 79 20 56 5 89 203 108 27 15 158 99 111 389 174 123 59 289 78 17 21 35 275 191 18 102 60 93 101 11 30 79 45 63 91 60 22 110 11 27 11 67 36 85 207 47 39 83 156 189 107 27 81 247 81 335 33 144 59 49 54 347 233 175 ...
result:
wrong answer 4th numbers differ - expected: '6', found: '18'