QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#678232#9519. Build a Computerucup-team987#AC ✓0ms3820kbC++204.0kb2024-10-26 14:22:422024-10-26 14:22:43

Judging History

This is the latest submission verdict.

  • [2024-10-26 14:22:43]
  • Judged
  • Verdict: AC
  • Time: 0ms
  • Memory: 3820kb
  • [2024-10-26 14:22:42]
  • Submitted

answer

#if __INCLUDE_LEVEL__ == 0

#include __BASE_FILE__

void Solve() {
  int L, R;
  IN(L, R);
  vector<tuple<int, int, int>> edges;
  for (int i : Rep(80, 100)) {
    edges.emplace_back(i, i + 1, 0);
    edges.emplace_back(i, i + 1, 1);
  }
  int nxt = 1;
  for (int k : Rep1(1, 20)) {
    int l = max(L, 1 << (k - 1));
    int r = min(R, (1 << k) - 1);
    if (r < l) {
      continue;
    }
    if (r - l + 1 == 1 << (k - 1)) {
      edges.emplace_back(0, 100 - k + 1, 1);
      continue;
    }

    string s(k, '0');
    string t(k, '0');
    for (int i : Rep(0, k)) {
      if (l >> (k - i - 1) & 1) {
        s[i] = '1';
      }
      if (r >> (k - i - 1) & 1) {
        t[i] = '1';
      }
    }

    int pl = 0, pr = 0;
    bool same = true;
    for (int i : Rep(0, k)) {
      if (s[i] < t[i]) {
        same = false;
      }
      int nl, nr;
      if (i + 1 == k) {
        nl = nr = 100;
      } else if (same) {
        nl = nr = nxt++;
      } else {
        nl = nxt++;
        nr = nxt++;
      }

      if (same) {
        edges.emplace_back(pl, nl, s[i] - '0');
      } else {
        edges.emplace_back(pl, nl, s[i] - '0');
        edges.emplace_back(pr, nr, t[i] - '0');
        if (pl != pr && s[i] == '0') {
          edges.emplace_back(pl, 100 - (k - i - 1), 1);
        }
        if (pl != pr && t[i] == '1') {
          edges.emplace_back(pr, 100 - (k - i - 1), 0);
        }
      }

      pl = nl;
      pr = nr;
    }
  }

  vector<bool> need(101, true);
  {
    vector<vector<int>> g(101);
    for (auto [i, j, x] : edges) {
      g[i].push_back(j);
    }
    vector<bool> f(101);
    f[0] = 1;
    for (int i : Rep(0, 100)) {
      if (f[i]) {
        for (int j : g[i]) {
          f[j] = true;
        }
      }
    }
    for (int i : Rep1(0, 100)) {
      if (!f[i]) {
        need[i] = false;
      }
    }
  }
  {
    vector<vector<int>> g(101);
    for (auto [i, j, x] : edges) {
      g[j].push_back(i);
    }
    vector<bool> f(101);
    f[100] = 1;
    for (int i : Rev(Rep1(1, 100))) {
      if (f[i]) {
        for (int j : g[i]) {
          f[j] = true;
        }
      }
    }
    for (int i : Rep1(0, 100)) {
      if (!f[i]) {
        need[i] = false;
      }
    }
  }
  vector<int> U;
  for (int i : Rep1(0, 100)) {
    if (need[i]) {
      U.push_back(i);
    }
  }
  OUT(Sz(U));
  vector<vector<pair<int, int>>> g(Sz(U));
  for (auto [i, j, x] : edges) {
    if (!need[i] || !need[j]) {
      continue;
    }
    i = int(ranges::lower_bound(U, i) - U.begin());
    j = int(ranges::lower_bound(U, j) - U.begin());
    g[i].emplace_back(j + 1, x);
  }
  for (int i : Rep(0, Sz(g))) {
    OUT(Sz(g[i]), g[i]);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  Solve();
}

#elif __INCLUDE_LEVEL__ == 1

#include <bits/stdc++.h>

template <class T> concept Range = std::ranges::range<T> && !std::convertible_to<T, std::string_view>;
template <class T> concept Tuple = std::__is_tuple_like<T>::value && !Range<T>;

namespace std {

istream& operator>>(istream& is, Range auto&& r) {
  for (auto&& e : r) is >> e;
  return is;
}
istream& operator>>(istream& is, Tuple auto&& t) {
  apply([&](auto&... xs) { (is >> ... >> xs); }, t);
  return is;
}

ostream& operator<<(ostream& os, Range auto&& r) {
  auto sep = "";
  for (auto&& e : r) os << exchange(sep, " ") << e;
  return os;
}
ostream& operator<<(ostream& os, Tuple auto&& t) {
  auto sep = "";
  apply([&](auto&... xs) { ((os << exchange(sep, " ") << xs), ...); }, t);
  return os;
}

}  // namespace std

using namespace std;

#define Rev views::reverse
#define Rep(...) [](int l, int r) { return views::iota(min(l, r), r); }(__VA_ARGS__)
#define Rep1(...) [](int l, int r) { return Rep(l, r + 1); }(__VA_ARGS__)
#define Sz(r) int(size(r))
#define IN(...) (cin >> forward_as_tuple(__VA_ARGS__))
#define OUT(...) (cout << forward_as_tuple(__VA_ARGS__) << '\n')

#endif  // __INCLUDE_LEVEL__ == 1

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

詳細信息

Test #1:

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

input:

5 7

output:

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

result:

ok ok

Test #2:

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

input:

10 27

output:

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

result:

ok ok

Test #3:

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

input:

5 13

output:

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

result:

ok ok

Test #4:

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

input:

1 1000000

output:

57
20 57 1 56 1 55 1 54 1 53 1 52 1 51 1 50 1 49 1 48 1 47 1 46 1 45 1 44 1 43 1 42 1 41 1 40 1 39 1 2 1
2 3 0 4 1
2 5 0 40 1
2 6 1 40 0
2 7 0 41 1
2 8 1 41 0
2 9 0 42 1
1 10 0
2 11 0 43 1
2 12 1 43 0
2 13 0 44 1
1 14 0
2 15 0 45 1
1 16 0
2 17 0 46 1
1 18 0
2 19 0 47 1
1 20 0
2 21 0 48 1
2 22 1 48 0...

result:

ok ok

Test #5:

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

input:

1 1

output:

2
1 2 1
0 

result:

ok ok

Test #6:

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

input:

7 9

output:

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

result:

ok ok

Test #7:

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

input:

3 7

output:

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

result:

ok ok

Test #8:

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

input:

1 5

output:

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

result:

ok ok

Test #9:

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

input:

1 4

output:

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

result:

ok ok

Test #10:

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

input:

8 9

output:

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

result:

ok ok

Test #11:

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

input:

7 51

output:

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

result:

ok ok

Test #12:

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

input:

51 79

output:

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

result:

ok ok

Test #13:

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

input:

92 99

output:

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

result:

ok ok

Test #14:

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

input:

27 36

output:

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

result:

ok ok

Test #15:

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

input:

55 84

output:

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

result:

ok ok

Test #16:

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

input:

297208 929600

output:

91
2 2 1 37 1
2 3 0 4 1
2 5 0 75 1
2 6 1 75 0
1 7 1
2 8 1 76 0
2 9 0 77 1
2 10 1 77 0
2 11 0 78 1
2 12 1 78 0
2 13 0 79 1
2 14 1 79 0
1 15 1
2 16 1 80 0
2 17 0 81 1
2 18 1 81 0
2 19 0 82 1
2 20 1 82 0
2 21 0 83 1
2 22 1 83 0
1 23 1
2 24 1 84 0
1 25 1
2 26 1 85 0
1 27 1
2 28 1 86 0
1 29 1
2 30 1 87 0...

result:

ok ok

Test #17:

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

input:

45728 589156

output:

83
5 2 1 67 1 66 1 65 1 31 1
2 3 0 4 1
1 5 1
2 6 1 70 0
1 7 1
2 8 1 71 0
2 9 0 72 1
2 10 1 72 0
2 11 0 73 1
2 12 1 73 0
1 13 1
2 14 1 74 0
2 15 0 75 1
2 16 1 75 0
1 17 1
2 18 1 76 0
2 19 0 77 1
2 20 1 77 0
1 21 1
2 22 1 78 0
2 23 0 79 1
2 24 1 79 0
2 25 0 80 1
2 26 1 80 0
2 27 0 81 1
2 28 1 81 0
2 2...

result:

ok ok

Test #18:

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

input:

129152 138000

output:

68
2 2 1 28 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
2 8 0 9 1
2 10 0 59 1
2 11 1 59 0
2 12 0 60 1
2 13 1 60 0
1 14 1
2 15 1 61 0
2 16 0 62 1
2 17 1 62 0
2 18 0 63 1
2 19 1 63 0
2 20 0 64 1
2 21 1 64 0
2 22 0 65 1
2 23 1 65 0
2 24 0 66 1
2 25 1 66 0
2 26 0 67 1
2 27 1 67 0
2 68 0 68 1
2 68 1 68 0
1 29 0
1 30...

result:

ok ok

Test #19:

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

input:

245280 654141

output:

86
3 2 1 68 1 33 1
1 3 1
1 4 1
2 5 0 6 1
1 7 1
2 8 1 73 0
1 9 1
2 10 1 74 0
1 11 1
2 12 1 75 0
1 13 1
2 14 1 76 0
1 15 1
2 16 1 77 0
2 17 0 78 1
2 18 1 78 0
2 19 0 79 1
2 20 1 79 0
2 21 0 80 1
2 22 1 80 0
1 23 1
2 24 1 81 0
2 25 0 82 1
2 26 1 82 0
2 27 0 83 1
2 28 1 83 0
2 29 0 84 1
2 30 1 84 0
2 31...

result:

ok ok

Test #20:

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

input:

202985 296000

output:

81
2 2 1 34 1
1 3 1
2 4 0 5 1
2 6 0 67 1
2 7 1 67 0
2 8 0 68 1
2 9 1 68 0
1 10 1
2 11 1 69 0
1 12 1
2 13 1 70 0
2 14 0 71 1
2 15 1 71 0
2 16 0 72 1
2 17 1 72 0
2 18 0 73 1
2 19 1 73 0
1 20 1
2 21 1 74 0
1 22 1
2 23 1 75 0
1 24 1
2 25 1 76 0
2 26 0 77 1
2 27 1 77 0
1 28 1
2 29 1 78 0
2 30 0 79 1
2 31...

result:

ok ok

Test #21:

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

input:

438671 951305

output:

90
2 2 1 36 1
1 3 1
2 4 0 5 1
1 6 1
2 7 1 75 0
2 8 0 76 1
2 9 1 76 0
1 10 1
2 11 1 77 0
1 12 1
2 13 1 78 0
2 14 0 79 1
2 15 1 79 0
2 16 0 80 1
2 17 1 80 0
2 18 0 81 1
2 19 1 81 0
1 20 1
2 21 1 82 0
1 22 1
2 23 1 83 0
2 24 0 84 1
2 25 1 84 0
2 26 0 85 1
2 27 1 85 0
2 28 0 86 1
2 29 1 86 0
1 30 1
2 31...

result:

ok ok

Test #22:

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

input:

425249 739633

output:

88
2 2 1 36 1
1 3 1
2 4 0 5 1
2 6 0 73 1
2 7 1 73 0
1 8 1
2 9 1 74 0
1 10 1
2 11 1 75 0
1 12 1
2 13 1 76 0
1 14 1
2 15 1 77 0
1 16 1
2 17 1 78 0
2 18 0 79 1
2 19 1 79 0
1 20 1
2 21 1 80 0
2 22 0 81 1
2 23 1 81 0
2 24 0 82 1
2 25 1 82 0
1 26 1
2 27 1 83 0
2 28 0 84 1
2 29 1 84 0
2 30 0 85 1
2 31 1 85...

result:

ok ok

Test #23:

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

input:

551207 961718

output:

56
1 2 1
2 3 0 4 1
2 5 0 39 1
2 6 1 39 0
2 7 0 40 1
1 8 0
2 9 0 41 1
2 10 1 41 0
1 11 1
1 12 0
1 13 1
2 14 1 43 0
2 15 0 44 1
1 16 0
1 17 1
2 18 1 45 0
2 19 0 46 1
2 20 1 46 0
2 21 0 47 1
1 22 0
1 23 1
1 24 0
2 25 0 49 1
2 26 1 49 0
2 27 0 50 1
1 28 0
1 29 1
2 30 1 51 0
2 31 0 52 1
2 32 1 52 0
2 33 ...

result:

ok ok

Test #24:

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

input:

114691 598186

output:

84
4 2 1 67 1 66 1 31 1
1 3 1
1 4 1
2 5 0 6 1
2 7 0 72 1
2 8 1 72 0
2 9 0 73 1
2 10 1 73 0
2 11 0 74 1
2 12 1 74 0
2 13 0 75 1
2 14 1 75 0
2 15 0 76 1
2 16 1 76 0
2 17 0 77 1
2 18 1 77 0
2 19 0 78 1
2 20 1 78 0
2 21 0 79 1
2 22 1 79 0
2 23 0 80 1
2 24 1 80 0
2 25 0 81 1
2 26 1 81 0
2 27 0 82 1
2 28 ...

result:

ok ok

Test #25:

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

input:

234654 253129

output:

46
1 2 1
1 3 1
1 4 1
2 5 0 6 1
2 7 0 33 1
1 8 0
1 9 1
2 10 1 34 0
2 11 0 35 1
2 12 1 35 0
1 13 1
2 14 1 36 0
2 15 0 37 1
1 16 0
2 17 0 38 1
1 18 0
1 19 1
2 20 1 39 0
2 21 0 40 1
2 22 1 40 0
2 23 0 41 1
1 24 0
1 25 1
1 26 0
1 27 1
2 28 1 43 0
1 29 1
1 30 0
1 31 1
1 32 0
2 46 0 46 1
2 46 1 46 0
2 34 0...

result:

ok ok

Test #26:

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

input:

554090 608599

output:

52
1 2 1
1 3 0
1 4 0
2 5 0 6 1
2 7 0 37 1
1 8 0
1 9 1
2 10 1 38 0
1 11 1
1 12 0
1 13 1
1 14 0
2 15 0 41 1
2 16 1 41 0
1 17 1
1 18 0
2 19 0 43 1
1 20 0
2 21 0 44 1
2 22 1 44 0
2 23 0 45 1
1 24 0
1 25 1
2 26 1 46 0
1 27 1
1 28 0
2 29 0 48 1
2 30 1 48 0
1 31 1
1 32 0
2 33 0 50 1
2 34 1 50 0
1 35 1
2 36...

result:

ok ok

Extra Test:

score: 0
Extra Test Passed