QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#781801 | #5117. Find Maximum | ZhZlzc | AC ✓ | 9ms | 3844kb | C++20 | 1.7kb | 2024-11-25 17:35:13 | 2024-11-25 17:35:14 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
using LL = long long;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
const int N = 1e6 + 10, M = 5010, mod = 998244353;
const int inf = 1e18;
mt19937_64 rng(time(0));
vector <int> pw;
int lim;
void solve() {
int l, r;
cin >> l >> r;
int hp = -1;
for(int i = lim - 1; i >= 0; i--){
if(r >= pw[i]){
hp = i;
break;
}
}
vector <int> bit(lim);
int res = 0, sum = l, hp2 = -1, temp = l;
for(int i = hp; i >= 0; i--){
int d = temp / pw[i];
if(d){
if(hp2 == -1) hp2 = i;
bit[i] = d;
temp -= d * pw[i];
res += d;
}
}
for(int i = 0; i <= hp; i++){
if(bit[i] == 2) continue;
if(bit[i] == 1){
if(sum + pw[i] <= r){
sum += pw[i];
res++;
hp2 = max(hp2, i);
}else break;
}else{
if(sum + 2 * pw[i] <= r){
sum += 2 * pw[i];
res += 2;
hp2 = max(hp2, i);
}else if(sum + pw[i] <= r){
sum += pw[i];
res++;
hp2 = max(hp2, i);
}else break;
}
}
res += hp2 + 1;
int d = r / pw[hp], d2 = l / pw[hp2];
if(hp == hp2 && d == d2){
cout << res << "\n";
return;
}
int res2 = hp + 1 + 1, sum2 = pw[hp];
for(int i = 0; i <= hp; i++){
if(sum2 + 2 * pw[i] <= r){
sum2 += 2 * pw[i];
res2 += 2;
}else if(sum2 + pw[i] <= r){
sum2 += pw[i];
res2++;
}else break;
}
//cout << res << " " << res2 << "\n";
cout << max(res, res2) << "\n";
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T = 1;
cin >> T;
pw.push_back(1);
int cur = 1;
while(cur <= inf){
cur *= 3LL;
pw.push_back(cur);
}
lim = pw.size();
while(T--) {
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3676kb
input:
10 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5
output:
3 3 4 5 3 4 5 4 5 5
result:
ok 10 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 3844kb
input:
5050 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 1 60 1 61...
output:
2 3 3 4 5 5 5 6 6 6 6 6 6 7 7 7 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 3 3 4 5 5 5 6 6 6 6 6 6 7 7 7 8 8 8 8 8 8 8...
result:
ok 5050 numbers
Test #3:
score: 0
Accepted
time: 9ms
memory: 3760kb
input:
10000 2924776299390853 348932224550662831 638290869233943020 897334616745111026 210780034220004669 279345354637770906 20574264013277469 387573622060864735 39441497975868873 806211034038773415 19845198891021950 243636832211738144 298454268109304380 988142879006387197 613847475002049291 86666797163210...
output:
110 112 109 110 112 108 113 112 110 107 109 113 110 111 111 111 109 108 111 113 111 111 113 112 111 110 111 108 111 110 111 111 112 111 113 109 111 110 108 111 111 113 110 110 110 112 110 107 111 111 109 107 112 111 110 111 112 111 111 112 111 111 109 111 110 111 112 111 113 110 113 112 112 110 110 ...
result:
ok 10000 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
144 3 8 2 8 2 9 3 9 9 26 8 26 8 27 9 27 27 80 26 80 26 81 27 81 81 242 80 242 80 243 81 243 243 728 242 728 242 729 243 729 729 2186 728 2186 728 2187 729 2187 2187 6560 2186 6560 2186 6561 2187 6561 6561 19682 6560 19682 6560 19683 6561 19683 19683 59048 19682 59048 19682 59049 19683 59049 59049 17...
output:
6 6 6 6 9 9 9 9 12 12 12 12 15 15 15 15 18 18 18 18 21 21 21 21 24 24 24 24 27 27 27 27 30 30 30 30 33 33 33 33 36 36 36 36 39 39 39 39 42 42 42 42 45 45 45 45 48 48 48 48 51 51 51 51 54 54 54 54 57 57 57 57 60 60 60 60 63 63 63 63 66 66 66 66 69 69 69 69 72 72 72 72 75 75 75 75 78 78 78 78 81 81 81...
result:
ok 144 numbers