QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#781801#5117. Find MaximumZhZlzcAC ✓9ms3844kbC++201.7kb2024-11-25 17:35:132024-11-25 17:35:14

Judging History

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

  • [2024-11-25 17:35:14]
  • 评测
  • 测评结果:AC
  • 用时:9ms
  • 内存:3844kb
  • [2024-11-25 17:35:13]
  • 提交

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