QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#123275#6510. Best Carry Player 3Si23WA 25ms1748kbC++142.8kb2023-07-11 23:56:092023-07-11 23:56:09

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-11 23:56:09]
  • 评测
  • 测评结果:WA
  • 用时:25ms
  • 内存:1748kb
  • [2023-07-11 23:56:09]
  • 提交

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((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(K & (1 << d))
                    steps++;
                else
                    steps += 2;
            }
            else if(K & (1 << 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;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 1748kb

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: 25ms
memory: 1744kb

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:

wrong answer 1940th numbers differ - expected: '2', found: '3'