QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#685400#9519. Build a Computerticking_away#AC ✓1ms3708kbC++202.5kb2024-10-28 19:16:272024-10-28 19:16:29

Judging History

This is the latest submission verdict.

  • [2024-10-28 19:16:29]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 3708kb
  • [2024-10-28 19:16:27]
  • Submitted

answer

#include <bits/stdc++.h>
#define con const
using namespace std;

using i32 = int32_t;
using i64 = int64_t;
#define i128 __int128_t
using u32 = uint32_t;
using u64 = uint64_t;
using f64 = long double;

template<class T>
using lque = priority_queue<T, vector<T>, greater<T>>;
template<class T>
using gque = priority_queue<T>;

template<class T>
void mes(T * arr, u32 n, int val) {
    memset(arr, val, n*sizeof(T));
}

template<u32 M, class N=u32>
u64 mpow(u64 x, N nth=M-2) {
    u64 res(x!=0||nth==0);
    for(; nth; x=(x*x)%M, nth>>=1)
        if(nth&1) res = (res*x)%M;
    return res;
}
// -------------------
con i32 MX = 100 + 7;
con i32 MOD = 998244353;

u32 l, r, lgl;
u32 ln[MX], rn[MX], ite=2;

// s = 1, t = 2;
u32 cu=2, ch=0;

vector<u32> vec;

void solve() {
    cout << ite << '\n';
    cout << vec.size();
    for(u32 v:vec) {
        cout << ' ' << v << " 1";
    }
    for(u32 u=2; u<=ite; ++u) {
        if(ln[u]&&rn[u]) {
            cout << "\n2 " << ln[u] << " 0 " << rn[u] << " 1";
        } else if(ln[u]) {
            cout << "\n1 " << ln[u] << " 0";
        } else if(rn[u]) {
            cout << "\n1 " << rn[u] << " 1";
        } else cout << "\n0";
    }
}

// 获取高度为h的满构造tree
u32 get_tree(u32 h) {
    if(h>ch) {
        u32 u = ++ite;
        if(h==1) {
            ln[u] = rn[u] = 2;
        } else {
            ln[u] = get_tree(h-1);
            rn[u] = ++ite;
            ln[rn[u]] = ln[ln[u]];
            rn[rn[u]] = rn[ln[u]];
        }
        ++ch;
        cu = u;
        return u;
    } else {
        u32 u = cu;
        for(u32 i=ch; i>h; --i)
            u = ln[u];
        return u;
    }
}

u32 build_tree(u32 l, u32 r, u32 lb, u32 rb) {
    if(l==lb&&rb==r) {
        u32 h = 0;
        while((1<<h)<(rb-lb)) ++h;
        return get_tree(h);
    } else {
        u32 u = lb?++ite:1, nl=0, nr=0;
        con u32 mid = (lb + rb) / 2;
        if(l<mid) nl = build_tree(l, min(mid, r), lb, mid);
        if(r>mid) nr = build_tree(max(l, mid), r, mid, rb);
        if(u!=1) {
            ln[u] = nl; rn[u] = nr;
        } else if(nr) {
            vec.push_back(nr);
        }
        return u;
    }
}

void pre() {
    cin >> l >> r;
    while((1<<lgl)<=r) ++lgl;
    build_tree(l, r+1, 0, 1<<lgl);
}

u32 _t = 1;
void init() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // cin >> _t;
}

int main() {
    init();
    for(;_t--;) {
        pre();
        solve();
    }
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3696kb

input:

5 7

output:

5
1 3 1
0
2 4 0 5 1
1 2 1
2 2 0 2 1

result:

ok ok

Test #2:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

10 27

output:

11
2 3 1 8 1
0
2 4 0 6 1
1 5 1
2 2 0 2 1
2 5 0 7 1
2 2 0 2 1
2 9 0 11 1
2 6 0 10 1
2 5 0 7 1
1 6 0

result:

ok ok

Test #3:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

5 13

output:

9
2 3 1 6 1
0
2 4 0 5 1
1 2 1
2 2 0 2 1
2 7 0 9 1
2 5 0 8 1
2 2 0 2 1
1 5 0

result:

ok ok

Test #4:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

1 1000000

output:

56
20 2 1 3 1 4 1 6 1 8 1 10 1 12 1 14 1 16 1 18 1 20 1 22 1 24 1 26 1 28 1 30 1 32 1 34 1 36 1 38 1
0
2 2 0 2 1
2 3 0 5 1
2 2 0 2 1
2 4 0 7 1
2 3 0 5 1
2 6 0 9 1
2 4 0 7 1
2 8 0 11 1
2 6 0 9 1
2 10 0 13 1
2 8 0 11 1
2 12 0 15 1
2 10 0 13 1
2 14 0 17 1
2 12 0 15 1
2 16 0 19 1
2 14 0 17 1
2 18 0 21 1...

result:

ok ok

Test #5:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

1 1

output:

2
1 2 1
0

result:

ok ok

Test #6:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

7 9

output:

7
2 3 1 5 1
0
1 4 1
1 2 1
1 6 0
1 7 0
2 2 0 2 1

result:

ok ok

Test #7:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

3 7

output:

6
2 3 1 4 1
0
1 2 1
2 5 0 6 1
2 2 0 2 1
2 2 0 2 1

result:

ok ok

Test #8:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

1 5

output:

4
3 2 1 3 1 4 1
0
2 2 0 2 1
1 3 0

result:

ok ok

Test #9:

score: 0
Accepted
time: 0ms
memory: 3696kb

input:

1 4

output:

5
3 2 1 3 1 4 1
0
2 2 0 2 1
1 5 0
1 2 0

result:

ok ok

Test #10:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

8 9

output:

5
1 3 1
0
1 4 0
1 5 0
2 2 0 2 1

result:

ok ok

Test #11:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

7 51

output:

14
4 3 1 5 1 10 1 12 1
0
1 4 1
1 2 1
2 6 0 9 1
2 7 0 8 1
2 2 0 2 1
2 2 0 2 1
2 7 0 8 1
2 5 0 11 1
2 6 0 9 1
2 10 0 13 1
1 14 0
1 6 0

result:

ok ok

Test #12:

score: 0
Accepted
time: 1ms
memory: 3648kb

input:

51 79

output:

16
2 3 1 13 1
0
1 4 1
2 5 0 11 1
2 6 0 8 1
1 7 1
1 2 1
2 9 0 10 1
2 2 0 2 1
2 2 0 2 1
2 8 0 12 1
2 9 0 10 1
1 14 0
1 15 0
2 11 0 16 1
2 8 0 12 1

result:

ok ok

Test #13:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

92 99

output:

12
1 3 1
0
2 4 0 10 1
1 5 1
1 6 1
1 7 1
2 8 0 9 1
2 2 0 2 1
2 2 0 2 1
1 11 0
1 12 0
1 7 0

result:

ok ok

Test #14:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

27 36

output:

14
2 3 1 10 1
0
1 4 1
2 5 0 7 1
1 6 1
1 2 1
2 8 0 9 1
2 2 0 2 1
2 2 0 2 1
1 11 0
1 12 0
2 7 0 13 1
1 14 0
1 2 0

result:

ok ok

Test #15:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

55 84

output:

20
2 3 1 13 1
0
1 4 1
2 5 0 8 1
1 6 1
1 7 1
1 2 1
2 9 0 12 1
2 10 0 11 1
2 2 0 2 1
2 2 0 2 1
2 10 0 11 1
1 14 0
2 15 0 17 1
2 8 0 16 1
2 9 0 12 1
1 18 0
2 9 0 19 1
1 20 0
1 2 0

result:

ok ok

Test #16:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

297208 929600

output:

71
2 3 1 51 1
0
2 4 0 49 1
2 5 0 45 1
1 6 1
2 7 0 43 1
2 8 0 41 1
2 9 0 37 1
1 10 1
2 11 0 35 1
2 12 0 33 1
2 13 0 23 1
1 14 1
1 15 1
1 16 1
1 17 1
1 18 1
2 19 0 22 1
2 20 0 21 1
2 2 0 2 1
2 2 0 2 1
2 20 0 21 1
2 24 0 32 1
2 25 0 31 1
2 26 0 30 1
2 27 0 29 1
2 18 0 28 1
2 19 0 22 1
2 18 0 28 1
2 27 ...

result:

ok ok

Test #17:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

45728 589156

output:

66
5 3 1 40 1 44 1 46 1 48 1
0
2 4 0 34 1
1 5 1
1 6 1
2 7 0 32 1
2 8 0 28 1
1 9 1
2 10 0 24 1
1 11 1
2 12 0 22 1
1 13 1
2 14 0 21 1
2 15 0 20 1
2 16 0 19 1
2 17 0 18 1
2 2 0 2 1
2 2 0 2 1
2 17 0 18 1
2 16 0 19 1
2 15 0 20 1
2 13 0 23 1
2 14 0 21 1
2 25 0 27 1
2 22 0 26 1
2 13 0 23 1
2 22 0 26 1
2 29...

result:

ok ok

Test #18:

score: 0
Accepted
time: 0ms
memory: 3708kb

input:

129152 138000

output:

51
2 3 1 31 1
0
1 4 1
1 5 1
1 6 1
1 7 1
1 8 1
2 9 0 29 1
2 10 0 27 1
2 11 0 25 1
1 12 1
2 13 0 24 1
2 14 0 23 1
2 15 0 22 1
2 16 0 21 1
2 17 0 20 1
2 18 0 19 1
2 2 0 2 1
2 2 0 2 1
2 18 0 19 1
2 17 0 20 1
2 16 0 21 1
2 15 0 22 1
2 14 0 23 1
2 12 0 26 1
2 13 0 24 1
2 25 0 28 1
2 12 0 26 1
2 27 0 30 1
...

result:

ok ok

Test #19:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

245280 654141

output:

67
3 3 1 42 1 50 1
0
1 4 1
1 5 1
2 6 0 30 1
1 7 1
1 8 1
1 9 1
1 10 1
1 11 1
2 12 0 28 1
2 13 0 26 1
2 14 0 24 1
1 15 1
2 16 0 23 1
2 17 0 22 1
2 18 0 21 1
2 19 0 20 1
2 2 0 2 1
2 2 0 2 1
2 19 0 20 1
2 18 0 21 1
2 17 0 22 1
2 15 0 25 1
2 16 0 23 1
2 24 0 27 1
2 15 0 25 1
2 26 0 29 1
2 24 0 27 1
2 31 ...

result:

ok ok

Test #20:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

202985 296000

output:

66
2 3 1 49 1
0
1 4 1
2 5 0 47 1
2 6 0 45 1
2 7 0 39 1
1 8 1
1 9 1
2 10 0 37 1
2 11 0 35 1
2 12 0 27 1
1 13 1
1 14 1
1 15 1
2 16 0 23 1
1 17 1
2 18 0 21 1
2 19 0 20 1
1 2 1
2 2 0 2 1
2 20 0 22 1
2 2 0 2 1
2 24 0 26 1
2 21 0 25 1
2 20 0 22 1
2 21 0 25 1
2 28 0 34 1
2 29 0 33 1
2 30 0 32 1
2 23 0 31 1...

result:

ok ok

Test #21:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

438671 951305

output:

73
2 3 1 52 1
0
1 4 1
2 5 0 48 1
1 6 1
2 7 0 42 1
1 8 1
1 9 1
2 10 0 40 1
2 11 0 38 1
2 12 0 32 1
1 13 1
1 14 1
2 15 0 30 1
2 16 0 28 1
2 17 0 21 1
1 18 1
1 19 1
1 20 1
1 2 1
2 22 0 27 1
2 23 0 26 1
2 24 0 25 1
2 2 0 2 1
2 2 0 2 1
2 24 0 25 1
2 23 0 26 1
2 21 0 29 1
2 22 0 27 1
2 28 0 31 1
2 21 0 29...

result:

ok ok

Test #22:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

425249 739633

output:

71
2 3 1 52 1
0
1 4 1
2 5 0 50 1
2 6 0 38 1
1 7 1
1 8 1
1 9 1
1 10 1
1 11 1
2 12 0 34 1
1 13 1
2 14 0 32 1
2 15 0 28 1
1 16 1
2 17 0 26 1
2 18 0 24 1
2 19 0 22 1
2 20 0 21 1
1 2 1
2 2 0 2 1
2 21 0 23 1
2 2 0 2 1
2 22 0 25 1
2 21 0 23 1
2 24 0 27 1
2 22 0 25 1
2 29 0 31 1
2 26 0 30 1
2 24 0 27 1
2 26...

result:

ok ok

Test #23:

score: 0
Accepted
time: 0ms
memory: 3700kb

input:

551207 961718

output:

72
1 3 1
0
2 4 0 55 1
2 5 0 53 1
2 6 0 51 1
2 7 0 45 1
1 8 1
1 9 1
2 10 0 41 1
1 11 1
2 12 0 39 1
2 13 0 35 1
1 14 1
2 15 0 33 1
2 16 0 29 1
1 17 1
2 18 0 27 1
2 19 0 22 1
1 20 1
1 21 1
1 2 1
2 23 0 26 1
2 24 0 25 1
2 2 0 2 1
2 2 0 2 1
2 24 0 25 1
2 22 0 28 1
2 23 0 26 1
2 30 0 32 1
2 27 0 31 1
2 22...

result:

ok ok

Test #24:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

114691 598186

output:

72
4 3 1 44 1 52 1 54 1
0
1 4 1
1 5 1
2 6 0 42 1
2 7 0 40 1
2 8 0 38 1
2 9 0 36 1
2 10 0 34 1
2 11 0 32 1
2 12 0 30 1
2 13 0 28 1
2 14 0 26 1
2 15 0 24 1
2 16 0 22 1
2 17 0 19 1
1 18 1
1 2 1
2 20 0 21 1
2 2 0 2 1
2 2 0 2 1
2 19 0 23 1
2 20 0 21 1
2 22 0 25 1
2 19 0 23 1
2 24 0 27 1
2 22 0 25 1
2 26 ...

result:

ok ok

Test #25:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

234654 253129

output:

56
1 3 1
0
1 4 1
1 5 1
2 6 0 44 1
2 7 0 40 1
1 8 1
2 9 0 36 1
1 10 1
2 11 0 34 1
2 12 0 30 1
1 13 1
2 14 0 28 1
2 15 0 20 1
1 16 1
1 17 1
1 18 1
1 19 1
2 2 0 2 1
2 21 0 27 1
2 22 0 26 1
2 23 0 25 1
2 19 0 24 1
2 2 0 2 1
2 19 0 24 1
2 23 0 25 1
2 22 0 26 1
2 20 0 29 1
2 21 0 27 1
2 31 0 33 1
2 28 0 3...

result:

ok ok

Test #26:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

554090 608599

output:

62
1 3 1
0
1 4 0
1 5 0
2 6 0 50 1
2 7 0 42 1
1 8 1
1 9 1
1 10 1
2 11 0 38 1
1 12 1
2 13 0 36 1
2 14 0 34 1
2 15 0 28 1
1 16 1
1 17 1
2 18 0 24 1
1 19 1
2 20 0 22 1
1 21 1
2 2 0 2 1
2 21 0 23 1
2 2 0 2 1
2 25 0 27 1
2 22 0 26 1
2 21 0 23 1
2 22 0 26 1
2 29 0 33 1
2 30 0 32 1
2 24 0 31 1
2 25 0 27 1
2...

result:

ok ok

Extra Test:

score: 0
Extra Test Passed