QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#122893#6510. Best Carry Player 3training4usacoTL 126ms3388kbC++232.9kb2023-07-11 13:57:582023-07-11 13:58:01

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 13:58:01]
  • 评测
  • 测评结果:TL
  • 用时:126ms
  • 内存:3388kb
  • [2023-07-11 13:57:58]
  • 提交

answer

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
 
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
 
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
 
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
 
#define int long long
using namespace std;
 
const int INF = 1e9 + 7;
const int MAXN = 505;
const int MAXM = 2.5e4 + 5;

int x, y, k;

int dist(int a, int b) {
    if(a == b) return 0;
    if((a ^ b) <= k || (abs(a - b) == 1)) return 1;
    return 2;
}

void solve() {
    cin >> x >> y >> k;
    if(x > y) swap(x, y);
    
    if(k <= 1) { 
        cout << abs(x - y) << endl; return;
    }
    
    int t = 0;
    while((1 << t) <= k) ++t;
    
    int blocksz = (1 << t);
    int numblocks = y / blocksz - x / blocksz;
    // cout << "numblocks: " << numblocks << endl;
    if(x / blocksz == y / blocksz) cout << dist(x % blocksz, y % blocksz) << endl;
    else cout << dist(0, y % blocksz) + dist(x % blocksz, blocksz - 1) + (numblocks - 1) * dist(0, blocksz - 1) + numblocks << endl;
    // cout << dist(0, y % blocksz) << " " << dist(x % blocksz, blocksz - 1) << "(" << x % blocksz << " " << blocksz - 1 << ") " << (numblocks - 1) * dist(0, blocksz - 1) << " " << numblocks << endl;
    // dist to reduce y down + dist to bring x up + dist for each block * number of blocks + 1 per block to actually transition between blocks
}

signed main() {
    int t; cin >> t;
    while(t--) solve();
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3388kb

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: 126ms
memory: 3384kb

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: 113ms
memory: 3356kb

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: -100
Time Limit Exceeded

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:


result: