QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#391890 | #5117. Find Maximum | wdw | WA | 1ms | 3676kb | C++20 | 1.8kb | 2024-04-16 21:35:22 | 2024-04-16 21:35:23 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
using ll = long long;
using ld = double;
using i64 = int64_t;
const int N = 3e5+5;
const ll mod = 998244353;
const ll inf = 1e18+5;
#define endl '\n'
vector<int>px;
vector<int>a(100);
void solve()
{
int l,r;
cin>>l>>r;
int num=0;
if(r<=99){
int ans=0;
for(int i=l;i<=r;i++){
ans=max(ans,a[i]);
}
cout<<ans<<endl;
}else {
while (1) {
auto y1 = std::upper_bound(px.begin(), px.end(), l) - px.begin();
auto y2 = std::upper_bound(px.begin(), px.end(), r) - px.begin();
if (y1 == y2) {
l /= 3;
r /= 3;
if(l==0&&r==0){
cout << num + y2+ 2 << '\n';
return;
}
num++;
} else {
cout << num + y2+ 2 << '\n';
return;
}
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// cout<<fixed<<setprecision(12);
// srand(time(NULL));
int w=2,lx=1,f=1;
int a1=1,a2=2,a3=1;
a[0]=1;
for(int i=1;i<=99;i++){
if(i%3==0){
a[i]=a[i/3]+1;
}else{
a[i]=a[i-1]+1;
}
}
while(lx<=1e18){
if(f==1){
lx+=a1;
a1*=3;
f++;
}else if(f==2){
lx+=a2;
a2*=3;
f++;
}else{
lx+=a3;
a3*=3;
f=1;
}
w++;
px.push_back(lx);
// cout<<lx<<" ";
}
int T=1;
cin >> T;
while(T--){
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3616kb
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: -100
Wrong Answer
time: 1ms
memory: 3676kb
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:
wrong answer 4840th numbers differ - expected: '12', found: '6'