QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#122893 | #6510. Best Carry Player 3 | training4usaco | TL | 126ms | 3388kb | C++23 | 2.9kb | 2023-07-11 13:57:58 | 2023-07-11 13:58:01 |
Judging History
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...