oj.uz

Submission #1079943

# Submission time Handle Problem Language Result Execution time Memory
1079943 2024-08-29T04:35:22 Z juicy Mechanical Doll (IOI18_doll) C++17
100 / 100
 110 ms 10256 KB 
#include "doll.h"

#include <bits/stdc++.h>

using namespace std;

void create_circuit(int m, vector<int> a) {
  a.push_back(0);
  int n = a.size(), s = 1;
  while (s < n) {
    s *= 2;
  }
  vector<int> lt, rt;
  lt.reserve(s);
  rt.reserve(s);
  function<int(int, int)> bld = [&](int l, int r) -> int {
    if (l >= n) {
      return -1;
    }
    if (l == r) {
      return 0;
    }
    int md = (l + r) / 2;
    lt.push_back(0);
    rt.push_back(0);
    int ind = lt.size();
    lt[ind - 1]= bld(l, md);
    rt[ind - 1] = bld(md + 1, r);
    return -ind;
  };
  bld(0, s - 1);
  int node = lt.size();
  vector<int> side(node);
  function<int(int)> crawl = [&](int u) {
    side[u] ^= 1;
    int v = side[u] ? rt[u] : lt[u];
    return !v ? u : crawl(-1 - v);
  };
  for (int x : a) {
    int u = crawl(0);
    (side[u] ? rt[u] : lt[u]) = x;
  }
  answer(vector<int>(m + 1, -1), rt, lt);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 35 ms 3976 KB Output is correct
3 Correct 39 ms 3904 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 52 ms 5684 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 35 ms 3976 KB Output is correct
3 Correct 39 ms 3904 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 52 ms 5684 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 69 ms 6752 KB Output is correct
9 Correct 70 ms 7232 KB Output is correct
10 Correct 110 ms 10256 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 35 ms 3976 KB Output is correct
3 Correct 39 ms 3904 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 52 ms 5684 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 69 ms 6752 KB Output is correct
9 Correct 70 ms 7232 KB Output is correct
10 Correct 110 ms 10256 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 103 ms 9972 KB Output is correct
15 Correct 76 ms 6464 KB Output is correct
16 Correct 104 ms 9612 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 107 ms 9892 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 65 ms 5924 KB Output is correct
3 Correct 66 ms 5740 KB Output is correct
4 Correct 101 ms 8772 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 65 ms 5924 KB Output is correct
3 Correct 66 ms 5740 KB Output is correct
4 Correct 101 ms 8772 KB Output is correct
5 Correct 101 ms 9488 KB Output is correct
6 Correct 102 ms 9268 KB Output is correct
7 Correct 100 ms 9492 KB Output is correct
8 Correct 102 ms 9072 KB Output is correct
9 Correct 69 ms 5968 KB Output is correct
10 Correct 98 ms 8976 KB Output is correct
11 Correct 98 ms 8824 KB Output is correct
12 Correct 66 ms 5968 KB Output is correct
13 Correct 68 ms 6208 KB Output is correct
14 Correct 71 ms 6208 KB Output is correct
15 Correct 68 ms 6236 KB Output is correct
16 Correct 2 ms 600 KB Output is correct
17 Correct 59 ms 6796 KB Output is correct
18 Correct 67 ms 5740 KB Output is correct
19 Correct 66 ms 5964 KB Output is correct
20 Correct 101 ms 8980 KB Output is correct
21 Correct 98 ms 8768 KB Output is correct
22 Correct 98 ms 8768 KB Output is correct