QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#704935#9519. Build a Computerchzhc_AC ✓6ms3816kbC++145.4kb2024-11-02 21:34:042024-11-02 21:34:07

Judging History

This is the latest submission verdict.

  • [2024-11-02 21:34:07]
  • Judged
  • Verdict: AC
  • Time: 6ms
  • Memory: 3816kb
  • [2024-11-02 21:34:04]
  • Submitted

answer

#include <bits/stdc++.h>

template < typename T >
inline void read(T &cnt) {
    cnt = 0; char ch = getchar(); bool op = 1;
    for (; ! isdigit(ch); ch = getchar())
        if (ch == '-') op = 0;
    for (; isdigit(ch); ch = getchar())
        cnt = cnt * 10 + ch - 48;
    cnt = op ? cnt : - cnt;
}


const int N = 200;
int max = 0;
std::vector < std::pair < int, int > > V[N], V2[N];
int change[N], Ichange[N], exi2[N];

inline void ADD(int u, int v, int x) {
    exi2[u] = 1, exi2[v] = 1;
    max = std::max(max, std::max(u, v));
    V[u].push_back(std::make_pair(v, x));
    // std::cout << u << ' ' << v << ' ' << x << '\n';
}
bool exi[200];
int nxt[N * N], head[N], to[N * N], val[N * N], In[N], TOT;
inline void add(int u, int v, int x) {
    nxt[++ TOT] = head[u];
    head[u] = TOT;
    to[TOT] = v;
    val[TOT] = x;
    In[v] ++;
    // std::cout << u << ' ' << v << ' ' << x << '\n';
}
int fir, FIR;
int EDGE[200][200][2];
inline void EXadd(int u, int v, int x) {
    if (EDGE[u][v][x]) return;
    EDGE[u][v][x] = 1;
    exi2[u] = 1, exi2[v] = 1;
    max = std::max(max, std::max(u, v));
    V2[u].push_back(std::make_pair(v, x));
    // std::cout << u << ' ' << v << ' ' << x << '\n';
}

inline void search(int u, int exist) {
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        // std::cout << v << 'q';
        if (val[i] == 1) {
            if (exist == 0) EXadd(FIR, v, 1);
            else EXadd(u, v, 1);
            search(v, 1);
        }
        else {
            if (exist == 0) search(v, 0);
            else EXadd(u, v, 0), search(v, 1);
        }
    }
}
int size;

inline void solve() {
    memset(exi2, 0, sizeof(exi2));
    max = 0;
    int fir = 0;
    for (int i = 1; i <= size; ++ i) {
        if (In[i] == 0) fir = i, FIR = i;
    }
    // std::cout << "JKDSA" << fir << '\n';
    search(fir, 0);

    int tot = 0;
    for (int i = 1; i <= 100; ++ i) {
        if (exi2[i]) {
            change[i] = ++ tot;
            Ichange[tot] = i;
        }
    }
    std::cout << tot << '\n';
    for (int i = 1; i <= tot; ++ i) {
        int siz = V2[Ichange[i]].size();
        std::cout << siz << ' ';
        for (int j = 0; j < siz; ++ j) {
            // add(i, change[V[Ichange[i]][j].first], V[Ichange[i]][j].second);
            std::cout << change[V2[Ichange[i]][j].first] << ' ' << V2[Ichange[i]][j].second << ' ';
        }
        std::cout << '\n';

    }
}
int main()
{   
    int l, r;
    read(l), read(r);

    if (l == r) {
        int x = 0;
        for (int i = 22; i >= 0; -- i)
            if ((l >> i) & 1) {
                x = i;
                break;
            }
        for (int i = x; i >= 0; -- i) {
            if ((l >> i) & 1) {
                ADD(i + 2, i + 1, 1);
            }
            else ADD(i + 2, i + 1, 0);
        }
    }
    else {
        int x = 25, x2 = 0, x3;
    for (int i = 22; i >= 0; -- i) {
        if ((((l >> i) & 1) == 0) && (((r >> i) & 1) == 1)) {
            x2 = i; x3 = x;
            break;
        }
        if ((((l >> i) & 1) == 1) && (((r >> i) & 1) == 1)) {
            ADD(x, x + 1, 1);
            x ++;
        }
        if ((((l >> i) & 1) == 0) && (((r >> i) & 1) == 0)) {
            ADD(x, x + 1, 0);
            x ++;
        }
    }
    for (int i = x2; i > 0; -- i) {
        if (((l >> i) & 1) == 0) {
            if (i == x2) {
                ADD(x, x + 1, 0);
                x += 1;
            }
            else {
                ADD(x, i + 1, 1);
                exi[i + 1] = 1;
                ADD(x, x + 1, 0);
                x ++;
            }
        }
        else {
            ADD(x, x + 1, 1);
            x ++;
        }
    }

    if (l & 1) {
        ADD(x, 1, 1);
    }
    else {
        ADD(x, 1, 1);
        ADD(x, 1, 0);
    }

    for (int i = x2; i > 0; -- i) {
        if (((r >> i) & 1) == 0) {
            if (i == x2) {
                ADD(x3, x + 1, 0);
                x ++;
            }
            else {
                ADD(x, x + 1, 0);
                x ++;
            }
        }
        else {
            if (i == x2) {
                ADD(x3, x + 1, 1);
                x ++;
            }
            else {
                ADD(x, i + 1, 0);
                exi[i + 1] = 1;
                ADD(x, x + 1, 1);
                x ++;
            }
        }
    }

    if (r & 1) {
        ADD(x, 1, 0);
        ADD(x, 1, 1);
    }
    else {
        ADD(x, 1, 0);
    }

    for (int i = 21; i >= 1; -- i) {
        if (exi[i]) {
            for (int j = i; j >= 2; -- j) {
                ADD(j, j - 1, 0), ADD(j, j - 1, 1);
            }
            break;
        }
    }
    }
    int tot = 0;
    for (int i = 1; i <= 100; ++ i) {
        if (exi2[i]) {
            change[i] = ++ tot;
            Ichange[tot] = i;
        }
    }
    size = tot;
    // std::cout << tot << '\n';
    for (int i = 1; i <= tot; ++ i) {
        int siz = V[Ichange[i]].size();
        // std::cout << siz << ' ';
        for (int j = 0; j < siz; ++ j) {
            add(i, change[V[Ichange[i]][j].first], V[Ichange[i]][j].second);
            // std::cout << change[V[Ichange[i]][j].first] << ' ' << V[Ichange[i]][j].second << ' ';
        }
        // std::cout << '\n';

    }

    solve();
    return 0;
}

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

詳細信息

Test #1:

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

input:

5 7

output:

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

result:

ok ok

Test #2:

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

input:

10 27

output:

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

result:

ok ok

Test #3:

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

input:

5 13

output:

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

result:

ok ok

Test #4:

score: 0
Accepted
time: 6ms
memory: 3656kb

input:

1 1000000

output:

39
0 
2 1 1 1 0 
2 2 1 2 0 
2 3 1 3 0 
2 4 1 4 0 
2 5 1 5 0 
2 6 1 6 0 
2 7 1 7 0 
2 8 1 8 0 
2 9 1 9 0 
2 10 1 10 0 
2 11 1 11 0 
2 12 1 12 0 
2 13 1 13 0 
2 14 1 14 0 
2 15 1 15 0 
2 16 1 16 0 
2 17 1 17 0 
2 18 1 18 0 
20 21 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...

result:

ok ok

Test #5:

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

input:

1 1

output:

2
0 
1 1 1 

result:

ok ok

Test #6:

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

input:

7 9

output:

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

result:

ok ok

Test #7:

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

input:

3 7

output:

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

result:

ok ok

Test #8:

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

input:

1 5

output:

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

result:

ok ok

Test #9:

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

input:

1 4

output:

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

result:

ok ok

Test #10:

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

input:

8 9

output:

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

result:

ok ok

Test #11:

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

input:

7 51

output:

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

result:

ok ok

Test #12:

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

input:

51 79

output:

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

result:

ok ok

Test #13:

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

input:

92 99

output:

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

result:

ok ok

Test #14:

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

input:

27 36

output:

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

result:

ok ok

Test #15:

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

input:

55 84

output:

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

result:

ok ok

Test #16:

score: 0
Accepted
time: 4ms
memory: 3816kb

input:

297208 929600

output:

57
0 
2 1 1 1 0 
2 2 1 2 0 
2 3 1 3 0 
2 4 1 4 0 
2 5 1 5 0 
2 6 1 6 0 
2 7 1 7 0 
2 8 1 8 0 
2 9 1 9 0 
2 10 1 10 0 
2 11 1 11 0 
2 12 1 12 0 
2 13 1 13 0 
2 14 1 14 0 
2 15 1 15 0 
2 16 1 16 0 
2 17 1 17 0 
2 18 1 18 0 
2 39 1 21 1 
2 22 0 18 1 
2 23 0 17 1 
1 24 1 
2 25 0 15 1 
2 26 0 14 1 
2 27 ...

result:

ok ok

Test #17:

score: 0
Accepted
time: 3ms
memory: 3656kb

input:

45728 589156

output:

54
0 
2 1 1 1 0 
2 2 1 2 0 
2 3 1 3 0 
2 4 1 4 0 
2 5 1 5 0 
2 6 1 6 0 
2 7 1 7 0 
2 8 1 8 0 
2 9 1 9 0 
2 10 1 10 0 
2 11 1 11 0 
2 12 1 12 0 
2 13 1 13 0 
2 14 1 14 0 
2 15 1 15 0 
2 16 1 16 0 
2 17 1 17 0 
2 18 1 18 0 
5 36 1 21 1 17 1 18 1 19 1 
2 22 0 15 1 
1 23 1 
1 24 1 
2 25 0 12 1 
2 26 0 1...

result:

ok ok

Test #18:

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

input:

129152 138000

output:

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

result:

ok ok

Test #19:

score: 0
Accepted
time: 3ms
memory: 3816kb

input:

245280 654141

output:

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

result:

ok ok

Test #20:

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

input:

202985 296000

output:

52
0 
2 1 1 1 0 
2 2 1 2 0 
2 3 1 3 0 
2 4 1 4 0 
2 5 1 5 0 
2 6 1 6 0 
2 7 1 7 0 
2 8 1 8 0 
2 9 1 9 0 
2 10 1 10 0 
2 11 1 11 0 
2 12 1 12 0 
2 13 1 13 0 
2 14 1 14 0 
2 15 1 15 0 
2 35 1 18 1 
1 19 1 
2 20 0 16 1 
2 21 0 15 1 
2 22 0 14 1 
1 23 1 
1 24 1 
2 25 0 11 1 
2 26 0 10 1 
2 27 0 9 1 
1 2...

result:

ok ok

Test #21:

score: 0
Accepted
time: 3ms
memory: 3736kb

input:

438671 951305

output:

57
0 
2 1 1 1 0 
2 2 1 2 0 
2 3 1 3 0 
2 4 1 4 0 
2 5 1 5 0 
2 6 1 6 0 
2 7 1 7 0 
2 8 1 8 0 
2 9 1 9 0 
2 10 1 10 0 
2 11 1 11 0 
2 12 1 12 0 
2 13 1 13 0 
2 14 1 14 0 
2 15 1 15 0 
2 16 1 16 0 
2 17 1 17 0 
2 18 1 18 0 
2 39 1 21 1 
1 22 1 
2 23 0 17 1 
1 24 1 
2 25 0 15 1 
1 26 1 
1 27 1 
2 28 0 ...

result:

ok ok

Test #22:

score: 0
Accepted
time: 2ms
memory: 3792kb

input:

425249 739633

output:

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

result:

ok ok

Test #23:

score: 0
Accepted
time: 3ms
memory: 3716kb

input:

551207 961718

output:

56
0 
2 1 1 1 0 
2 2 1 2 0 
2 3 1 3 0 
2 4 1 4 0 
2 5 1 5 0 
2 6 1 6 0 
2 7 1 7 0 
2 8 1 8 0 
2 9 1 9 0 
2 10 1 10 0 
2 11 1 11 0 
2 12 1 12 0 
2 13 1 13 0 
2 14 1 14 0 
2 15 1 15 0 
2 16 1 16 0 
2 17 1 17 0 
1 20 1 
2 39 1 21 0 
2 22 0 18 1 
2 23 0 17 1 
2 24 0 16 1 
1 25 1 
1 26 1 
2 27 0 13 1 
1 ...

result:

ok ok

Test #24:

score: 0
Accepted
time: 4ms
memory: 3684kb

input:

114691 598186

output:

55
0 
2 1 1 1 0 
2 2 1 2 0 
2 3 1 3 0 
2 4 1 4 0 
2 5 1 5 0 
2 6 1 6 0 
2 7 1 7 0 
2 8 1 8 0 
2 9 1 9 0 
2 10 1 10 0 
2 11 1 11 0 
2 12 1 12 0 
2 13 1 13 0 
2 14 1 14 0 
2 15 1 15 0 
2 16 1 16 0 
2 17 1 17 0 
2 18 1 18 0 
4 37 1 21 1 18 1 19 1 
1 22 1 
1 23 1 
2 24 0 14 1 
2 25 0 13 1 
2 26 0 12 1 
...

result:

ok ok

Test #25:

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

input:

234654 253129

output:

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

result:

ok ok

Test #26:

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

input:

554090 608599

output:

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

result:

ok ok

Extra Test:

score: 0
Extra Test Passed