oj.uz

Submission #812237

# Submission time Handle Problem Language Result Execution time Memory
812237 2023-08-07T07:56:39 Z thimote75 Mechanical Doll (IOI18_doll) C++14
100 / 100
 93 ms 13252 KB 
#include "doll.h"

#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;
using bdata = vector<bool>;

using di = pair<int, int>;
using vd = vector<di>;

struct SegTree {
  idata treeIds;
  int rsize = 0;

  int start, height, size;

  void generate (int node, int limit, int end) {
    if (node == 0) return ;

    generate(node >> 1, (limit + 1) >> 1, end >> 1);
    if (node == start) return ;

    for (int u = end - limit; u < end; u ++)
      treeIds[u] = - ((rsize ++) + 1);
  }
  int getId (int node) {
    int count = 0;
    int diam  = height - 1;
    while (node != 1) {
      if (node & 1) count += 1 << diam;

      diam --;
      node >>= 1;
    }

    return count;
  }

  idata X, Y;
  SegTree (idata A) {
    size   = A.size();
    height = ceil(log2(size));
    start  = 1 << height;

    treeIds.resize(start << 1, - 1e9);

    generate(start, size, treeIds.size());

    vd g_pos;
    for (int i = treeIds.size() - size; i < treeIds.size(); i ++)
      g_pos.push_back({ getId( i ), i });
    
    sort(g_pos.begin(), g_pos.end());

    for (int i = 0; i < size; i ++)
      treeIds[g_pos [i].second] = A[i];
    
    X.resize(rsize); Y.resize(rsize);
    
    for (int i = 1; i < start; i ++) {
      if (treeIds[i] >= 0 || treeIds[i] == - 1e9) continue ;
      int xid = - (1 + treeIds[i]);

      int n0 = 2 * i;     int vn0 = treeIds[n0] == - 1e9 ? -1 : treeIds[n0];
      int n1 = 2 * i + 1; int vn1 = treeIds[n1] == - 1e9 ? -1 : treeIds[n1];
      X[xid] = vn0;
      Y[xid] = vn1;
    }
  }
};

void create_circuit(int M, vector<int> A) {
  A.push_back(0);
  idata C( M + 1, - 1 ); // - 1 is the decision tree root
  
  SegTree tree(A);
  
  idata X = tree.X;
  idata Y = tree.Y;

  answer(C, X, Y);
}

Compilation message

doll.cpp: In constructor 'SegTree::SegTree(idata)':
doll.cpp:52:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for (int i = treeIds.size() - size; i < treeIds.size(); i ++)
      |                                         ~~^~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 34 ms 5736 KB Output is correct
3 Correct 29 ms 5136 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 1448 KB Output is correct
6 Correct 45 ms 7200 KB Output is correct
7 Correct 0 ms 212 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 34 ms 5736 KB Output is correct
3 Correct 29 ms 5136 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 1448 KB Output is correct
6 Correct 45 ms 7200 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 53 ms 9368 KB Output is correct
9 Correct 54 ms 9708 KB Output is correct
10 Correct 83 ms 13252 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 300 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 34 ms 5736 KB Output is correct
3 Correct 29 ms 5136 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 1448 KB Output is correct
6 Correct 45 ms 7200 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 53 ms 9368 KB Output is correct
9 Correct 54 ms 9708 KB Output is correct
10 Correct 83 ms 13252 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 300 KB Output is correct
14 Correct 86 ms 12660 KB Output is correct
15 Correct 56 ms 9060 KB Output is correct
16 Correct 85 ms 12520 KB Output is correct
17 Correct 1 ms 296 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 88 ms 12740 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 69 ms 8148 KB Output is correct
3 Correct 47 ms 8216 KB Output is correct
4 Correct 93 ms 11100 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 69 ms 8148 KB Output is correct
3 Correct 47 ms 8216 KB Output is correct
4 Correct 93 ms 11100 KB Output is correct
5 Correct 84 ms 11292 KB Output is correct
6 Correct 77 ms 11180 KB Output is correct
7 Correct 82 ms 11332 KB Output is correct
8 Correct 78 ms 11164 KB Output is correct
9 Correct 48 ms 8132 KB Output is correct
10 Correct 79 ms 11184 KB Output is correct
11 Correct 77 ms 11148 KB Output is correct
12 Correct 47 ms 8204 KB Output is correct
13 Correct 51 ms 8168 KB Output is correct
14 Correct 54 ms 8292 KB Output is correct
15 Correct 49 ms 8256 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 46 ms 6584 KB Output is correct
18 Correct 47 ms 8212 KB Output is correct
19 Correct 47 ms 8072 KB Output is correct
20 Correct 75 ms 11164 KB Output is correct
21 Correct 76 ms 11112 KB Output is correct
22 Correct 76 ms 11108 KB Output is correct