oj.uz

Submission #720407

# Submission time Handle Problem Language Result Execution time Memory
720407 2023-04-08T07:55:38 Z LittleCube Mechanical Doll (IOI18_doll) C++14
100 / 100
 131 ms 12536 KB 
#include "doll.h"
#include <bits/stdc++.h>
// #ifndef EVAL
// #include "grader.cpp"
// #endif
using namespace std;

namespace
{
  int K = 0;
  vector<int> X, Y, A, state;
  int construct(int N, int sz)
  {
    if (sz == 1)
      return 0;
    else
    {
      int l = -1, r = -1, id = ++K;
      X.emplace_back(0);
      Y.emplace_back(0);
      if (N > sz / 2)
      {
        r = construct(sz / 2, sz / 2);
        l = construct(N - sz / 2, sz / 2);
      }
      else
        r = construct(N, sz / 2);
      X[id - 1] = l;
      Y[id - 1] = r;
      return -id;
    }
  }
  void dfs(int cur, int idx = 0)
  {
    if (cur == 0)
      return;
    if (cur > 0)
      dfs(-1, idx);
    if (cur < 0)
    {
      state[-cur - 1] ^= 1;
      int nxt = state[-cur - 1] ^ 1;
      if((nxt ? Y : X)[-cur - 1] == 0)
        (nxt ? Y : X)[-cur - 1] = A[idx++];
      dfs((nxt ? Y : X)[-cur - 1], idx);
    }
  }
};

void create_circuit(int M, vector<int> A)
{
  vector<int> C(M + 1, -1);

  A.emplace_back(0);
  int N = A.size(), lg = __lg(N - 1) + 1;
  ::A = A;
  construct(N, 1 << lg);
  state.resize(X.size());
  dfs(-1);

  answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 42 ms 4804 KB Output is correct
3 Correct 40 ms 4852 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 60 ms 6936 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 42 ms 4804 KB Output is correct
3 Correct 40 ms 4852 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 60 ms 6936 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 81 ms 8172 KB Output is correct
9 Correct 82 ms 8564 KB Output is correct
10 Correct 121 ms 12536 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 300 KB Output is correct
13 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 42 ms 4804 KB Output is correct
3 Correct 40 ms 4852 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 60 ms 6936 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 81 ms 8172 KB Output is correct
9 Correct 82 ms 8564 KB Output is correct
10 Correct 121 ms 12536 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 300 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 120 ms 12164 KB Output is correct
15 Correct 79 ms 7896 KB Output is correct
16 Correct 131 ms 12008 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 296 KB Output is correct
19 Correct 0 ms 300 KB Output is correct
20 Correct 121 ms 12240 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 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 76 ms 7048 KB Output is correct
3 Correct 74 ms 6980 KB Output is correct
4 Correct 114 ms 10660 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 76 ms 7048 KB Output is correct
3 Correct 74 ms 6980 KB Output is correct
4 Correct 114 ms 10660 KB Output is correct
5 Correct 118 ms 11768 KB Output is correct
6 Correct 119 ms 11724 KB Output is correct
7 Correct 118 ms 11788 KB Output is correct
8 Correct 120 ms 11424 KB Output is correct
9 Correct 74 ms 6980 KB Output is correct
10 Correct 112 ms 11404 KB Output is correct
11 Correct 118 ms 11004 KB Output is correct
12 Correct 75 ms 7264 KB Output is correct
13 Correct 78 ms 7656 KB Output is correct
14 Correct 82 ms 7660 KB Output is correct
15 Correct 77 ms 7888 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 71 ms 7720 KB Output is correct
18 Correct 77 ms 7256 KB Output is correct
19 Correct 73 ms 7264 KB Output is correct
20 Correct 116 ms 11264 KB Output is correct
21 Correct 121 ms 11012 KB Output is correct
22 Correct 109 ms 11092 KB Output is correct