oj.uz

Submission #102844

# Submission time Handle Problem Language Result Execution time Memory
102844 2019-03-28T01:01:26 Z wxh010910 Mechanical Doll (IOI18_doll) C++17
100 / 100
 114 ms 10788 KB 
#include <bits/stdc++.h>
#include "doll.h"

using namespace std;

const int inf = 0x3f3f3f3f;

void create_circuit(int m, vector<int> a) {
  int n = a.size(), base = 1;
  a.push_back(0);
  while (base < n) {
    base <<= 1;
  }
  vector<int> rev(base);
  for (int i = 0; i < base; ++i) {
    rev[i] = rev[i >> 1] >> 1 | (i & 1 ? base >> 1 : 0);
  }
  vector<int> real(base, -1);
  for (int i = base - n; i < base; ++i) {
    real[rev[i]] = i;
  }
  vector<int> id(base);
  for (int i = 0, total = 0; i < base; ++i) {
    if (~real[i]) {
      id[real[i]] = ++total;
    }
  }
  
  vector<int> x, y;
  
  function<int(int, int)> build = [&](int l, int r) {
    if (l == r - 1) {
      if (l >= base - n) {
        return a[id[l]];
      } else {
        return inf;
      }
    } else {
      int m = l + r >> 1;
      int left = build(l, m);
      int right = build(m, r);
      if (left == inf && right == inf) {
        return inf;
      } else {
        x.push_back(left);
        y.push_back(right);
        return -(int)x.size();
      }
    }
  };

  int root = build(0, base);
  vector<int> c(m + 1, root);
  c[0] = a[0];
  for (int i = 0; i < -root; ++i) {
    if (x[i] == inf) {
      x[i] = root;
    }
    if (y[i] == inf) {
      y[i] = root;
    }
  }
  answer(c, x, y);
}

Compilation message

doll.cpp: In lambda function:
doll.cpp:39:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |       int m = l + r >> 1;
      |               ~~^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 41 ms 4828 KB Output is correct
3 Correct 39 ms 4936 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 54 ms 6212 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 41 ms 4828 KB Output is correct
3 Correct 39 ms 4936 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 54 ms 6212 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 75 ms 8480 KB Output is correct
9 Correct 67 ms 8556 KB Output is correct
10 Correct 100 ms 10788 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 41 ms 4828 KB Output is correct
3 Correct 39 ms 4936 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 54 ms 6212 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 75 ms 8480 KB Output is correct
9 Correct 67 ms 8556 KB Output is correct
10 Correct 100 ms 10788 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 101 ms 10404 KB Output is correct
15 Correct 69 ms 7836 KB Output is correct
16 Correct 113 ms 10140 KB Output is correct
17 Correct 2 ms 204 KB Output is correct
18 Correct 2 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 94 ms 10536 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 51 ms 6944 KB Output is correct
3 Correct 75 ms 7404 KB Output is correct
4 Correct 77 ms 9640 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 51 ms 6944 KB Output is correct
3 Correct 75 ms 7404 KB Output is correct
4 Correct 77 ms 9640 KB Output is correct
5 Correct 102 ms 10012 KB Output is correct
6 Correct 91 ms 9864 KB Output is correct
7 Correct 94 ms 9892 KB Output is correct
8 Correct 101 ms 9704 KB Output is correct
9 Correct 55 ms 7468 KB Output is correct
10 Correct 89 ms 9640 KB Output is correct
11 Correct 80 ms 9644 KB Output is correct
12 Correct 56 ms 7444 KB Output is correct
13 Correct 81 ms 7444 KB Output is correct
14 Correct 76 ms 7628 KB Output is correct
15 Correct 63 ms 7760 KB Output is correct
16 Correct 3 ms 560 KB Output is correct
17 Correct 53 ms 7204 KB Output is correct
18 Correct 61 ms 7068 KB Output is correct
19 Correct 58 ms 7404 KB Output is correct
20 Correct 98 ms 9624 KB Output is correct
21 Correct 103 ms 9668 KB Output is correct
22 Correct 114 ms 9600 KB Output is correct