oj.uz

Submission #415847

# Submission time Handle Problem Language Result Execution time Memory
415847 2021-06-01T15:41:59 Z 2qbingxuan Mechanical Doll (IOI18_doll) C++14
100 / 100
 141 ms 11332 KB 
#include "doll.h"
#include <bits/stdc++.h>
#ifdef local
#define debug(x...) qqbx(#x, x)
template <typename ...T> void qqbx(const char *s, T ...a) {
    int cnt = sizeof...(T);
    ((std::cerr << "\e[1;32m(" << s << ") = ("), ... , (std::cerr << a << (--cnt ? ", " : "\e[0m)\n")));
}
#define pary(x...) danb(#x, x)
template <typename T> void danb(const char *s, T L, T R) {
    std::cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L)
        std::cerr << (f++ ? ", " : "") << *L;
    std::cerr << " ]\e[0m\n";
}
#else
#define debug(...) ((void)0)
#define pary(...) ((void)0)
#endif // local
#define all(v) begin(v),end(v)

using namespace std;
const int maxn = 800025;

int odd[maxn];
int ls[maxn], rs[maxn];
int leaf[maxn];
int counter = 0;
int build(int root, int lev) {
    if (lev == 0) {
        debug("LEAF");
        return -2;
    }
    int cur = counter++;
    ls[cur] = build(root, lev - 1);
    rs[cur] = build(root, lev - 1);
    return cur;
}

void dfs(vector<int> &A, int root, int cur, int a, int b) {
    if (ls[cur] != -1)
        dfs(A, root, ls[cur], a*2, b);
    else
        ls[cur] = b < A.size() ? A[b] : root;
    if (rs[cur] != -1)
        dfs(A, root, rs[cur], a*2, b+a);
    else
        rs[cur] = b+a < A.size() ? A[b+a] : root;
}
void create_circuit(int M, std::vector<int> A) {

  int N = A.size();
  int L = __lg(N) + 1;
  vector<int> aux(L);
  for (int i = 0; i < L; i++) {
      aux[i] = counter++;
  }

  vector<int> C(M + 1, -aux[0] - 1);
  for (int i = 0; i < L; i++) {
      if (i != 0)
          rs[aux[i-1]] = aux[i];
      int lev = L - 1 - i;
      debug(i);
      if (N >> lev & 1) {
          ls[aux[i]] = build(aux[0], lev);
      } else {
          ls[aux[i]] = aux[0];
      }
  }
  rs[aux[L-1]] = -1;

  int it = 0;
  int cur = aux[0];
  while (cur != -1) {
      debug(cur);
      int nxt = odd[cur] ? rs[cur] : ls[cur];
      if (nxt == -2) {
          debug("JIZZ");
          if (it < A.size()) {
              debug(A[it]);
              (odd[cur] ? rs[cur] : ls[cur]) = -A[it++]-1;
              nxt = aux[0];
          } else {
              nxt = (odd[cur] ? rs[cur] : ls[cur]) = aux[0];
          }
      }
      odd[cur] ^= 1;
      cur = nxt;
  }
  pary(odd, odd+counter);

  vector<int> X(counter), Y(counter);
  for (int i = 0; i < counter; i++) {
      X[i] = -ls[i]-1;
      Y[i] = -rs[i]-1;
  }

  answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void dfs(std::vector<int>&, int, int, int, int)':
doll.cpp:44:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         ls[cur] = b < A.size() ? A[b] : root;
      |                   ~~^~~~~~~~~~
doll.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         rs[cur] = b+a < A.size() ? A[b+a] : root;
      |                   ~~~~^~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:80:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |           if (it < A.size()) {
      |               ~~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 47 ms 4756 KB Output is correct
3 Correct 46 ms 4364 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1484 KB Output is correct
6 Correct 66 ms 6436 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 47 ms 4756 KB Output is correct
3 Correct 46 ms 4364 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1484 KB Output is correct
6 Correct 66 ms 6436 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 82 ms 7644 KB Output is correct
9 Correct 90 ms 7964 KB Output is correct
10 Correct 130 ms 11332 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 47 ms 4756 KB Output is correct
3 Correct 46 ms 4364 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1484 KB Output is correct
6 Correct 66 ms 6436 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 82 ms 7644 KB Output is correct
9 Correct 90 ms 7964 KB Output is correct
10 Correct 130 ms 11332 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 121 ms 10692 KB Output is correct
15 Correct 79 ms 7236 KB Output is correct
16 Correct 121 ms 10912 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 124 ms 11296 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 332 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 332 KB Output is correct
2 Correct 75 ms 6828 KB Output is correct
3 Correct 73 ms 6772 KB Output is correct
4 Correct 112 ms 9824 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 75 ms 6828 KB Output is correct
3 Correct 73 ms 6772 KB Output is correct
4 Correct 112 ms 9824 KB Output is correct
5 Correct 141 ms 10292 KB Output is correct
6 Correct 115 ms 10028 KB Output is correct
7 Correct 115 ms 10348 KB Output is correct
8 Correct 115 ms 10052 KB Output is correct
9 Correct 76 ms 6816 KB Output is correct
10 Correct 117 ms 10112 KB Output is correct
11 Correct 113 ms 9732 KB Output is correct
12 Correct 77 ms 6648 KB Output is correct
13 Correct 87 ms 6936 KB Output is correct
14 Correct 85 ms 7056 KB Output is correct
15 Correct 87 ms 6972 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 78 ms 6816 KB Output is correct
18 Correct 86 ms 6852 KB Output is correct
19 Correct 80 ms 6816 KB Output is correct
20 Correct 129 ms 10276 KB Output is correct
21 Correct 123 ms 10156 KB Output is correct
22 Correct 115 ms 10252 KB Output is correct