QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #123277 | #6510. Best Carry Player 3 | Si23 | WA | 53ms | 1744kb | C++14 | 2.8kb | 2023-07-12 00:47:05 | 2023-07-12 00:47:08 |
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;
ll 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\n");
continue;
}
if(K <= 1){
printf("%lld\n", llabs(X - Y));
continue;
}
ll steps = 0ll;
if(X > Y) swap(X, Y);
int d = digits(K + 1) - 1;
int y = digits(Y ^ X);
// 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(K & (1 << d))
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(K & (1 << d))
steps += 2;
else if((X & ones(d)) == ones(d)){
steps += 2;
}
else
steps += 3;
}
// printf("steps = %d\n", steps);
if(K & (1 << d)){
s[d] = 0ll;
s[d + 1] = 2ll;
}
else{
s[d] = 1ll;
s[d + 1] = 3ll;
}
for(int i = d + 2; i < y; i++)
s[i] = (s[i - 1] << 1ll) + 1ll;
// 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] + 1ll;
}
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 += 2ll;
else if ((Y & ones(d)) == 0)
steps += 2ll;
else
steps += 3ll;
}
}
printf("%lld\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: 0
Accepted
time: 25ms
memory: 1524kb
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 6 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 6 79 44 63 91 60 22 109 11 3 10 67 11 85 207 47 39 83 156 189 107 27 81 247 81 335 33 144 11 50 54 347 233 175 30 7...
result:
ok 100000 numbers
Test #3:
score: 0
Accepted
time: 11ms
memory: 1524kb
input:
100000 322 25 2699 83 407 606 157 77 162 358 3 4064 407 35 1145 15 491 801 174 95 1886 67 93 2573 415 7 2014 16 203 2003 95 357 453 287 14 1247 63 108 3617 124 30 3806 116 425 830 483 63 2237 97 123 1194 124 460 2729 71 99 818 118 24 527 92 236 3298 446 55 413 0 122 3335 193 64 318 55 201 3120 475 8...
output:
1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 6 1 1 1 1 3 1 1 1 3 1 1 1 1 1 1 1 1 5 1 1 1 1 1 1 2 1 1 1 1 6 1 1 1 6 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 114 1 1 1 1 1 1 1 1...
result:
ok 100000 numbers
Test #4:
score: 0
Accepted
time: 23ms
memory: 1520kb
input:
100000 460 16 1999514420 38 120 459071025 36 5 435961014 415 44 1634888670 236 110 1172545331 116 449 1722938168 9 55 1093539809 98 9 2009254678 160 13 874849076 72 59 307472779 94 278 829310177 375 21 1588655085 85 272 1310414813 101 309 2072973009 96 370 510582365 55 6 285781515 45 99 743723479 43...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 100000 numbers
Test #5:
score: 0
Accepted
time: 18ms
memory: 1744kb
input:
100000 102 211 434535176914392191 113 382 10473939473902551 154 70 347749780432060530 307 4 770301859497555482 21 88 1148164284941713103 141 52 298799672146159282 86 67 592474494235856008 126 423 500925453682730053 72 23 751099353059890065 105 60 591595972426609814 1 312 322398882693527462 488 21 29...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 100000 numbers
Test #6:
score: -100
Wrong Answer
time: 53ms
memory: 1560kb
input:
100000 900433230470865373 168 0 274936233345873548 263 0 107 912910047733415890 1 148108377912190269 159 1 637618261092082754 433 0 206160758979307706 117 5 374274670768546935 258 4 84 460392244654734212 6 568787141853147589 410 2 412 739540468281060656 2 420 372651009036366141 4 99 7542107804877648...
output:
900433230470865205 274936233345873285 912910047733415783 148108377912190110 637618261092082321 96914365681782555 204972384650278220 215906916105129522 376494912800658465 698164249355116719 183840378570219994 315011747744261508 158362367610232252 194765535009043001 364778850792502383 6516261605686012...
result:
wrong answer 6th numbers differ - expected: '77310284617240347', found: '96914365681782555'