oj.uz

Submission #836764

# Submission time Handle Problem Language Result Execution time Memory
836764 2023-08-24T15:23:54 Z Johann Mechanical Doll (IOI18_doll) C++14
100 / 100
 88 ms 11104 KB 
#include "doll.h"
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int switches;
vi X, Y;
vi A;
vi L;  // list of leaves
int d; // depth of binary tree

int newSwitch()
{
  X.push_back(0), Y.push_back(0);
  return --switches;
}
void setSwitch(vector<int> &XY, int switchnum, int dest)
{
  XY[-switchnum - 1] = dest;
}
int getSwitch(vector<int> &XY, int i) { return XY[-i - 1]; }
int reverseOrder(int i)
{
  int tmp = 0;
  for (int j = 0; j < d; ++j)
    if ((1 << j) & i)
      tmp |= (1 << (d - j - 1));
  return tmp;
}
int buildTree(int base, int j)
{
  if (j == d)
  {
    int idx = lower_bound(all(L), base) - L.begin();
    return A[idx];
  }
  else
  {
    int sw = newSwitch();
    setSwitch(X, sw, buildTree(base, j + 1));
    setSwitch(Y, sw, buildTree((1 << j) | base, j + 1));
    return sw;
  }
}

void create_circuit(int M, std::vector<int> _A)
{
  A = _A;
  int N = A.size();
  switches = 0;
  vi C(M + 1);

  vi order(M + 1, 0);
  order[0] = 1;
  for (int i = 0; i < sz(A); ++i)
    ++order[A[i]];
  int firstSwitch = newSwitch();
  for (int i = 0; i < sz(order); ++i)
    if (order[i] == 0)
      C[i] = 0;
    else
      C[i] = firstSwitch;

  d = 0;
  while ((1 << d) < N + 1)
    ++d;

  for (int j = 0; j < d; ++j)
  {
    int subtreesize = (1 << (d - j - 1));
    if (N & subtreesize)
      for (int i = 0; i < subtreesize; ++i)
        L.push_back((i << (j + 1)) | ((1 << j) - 1));
  }

  sort(all(L));

  vi line(1, firstSwitch);
  for (int j = 0; j < d; ++j)
  {
    int sw = line[j];
    int base = (1 << j) - 1;

    if (N & (1 << (d - j - 1)))
      setSwitch(X, sw, buildTree(base, j + 1));
    else
      setSwitch(X, sw, firstSwitch);

    if (j < d - 1)
    {
      line.push_back(newSwitch());
      setSwitch(Y, sw, line.back());
    }
    else
      setSwitch(Y, sw, 0);
  }

  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 30 ms 4872 KB Output is correct
3 Correct 28 ms 4800 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 1876 KB Output is correct
6 Correct 41 ms 6604 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 30 ms 4872 KB Output is correct
3 Correct 28 ms 4800 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 1876 KB Output is correct
6 Correct 41 ms 6604 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 49 ms 8176 KB Output is correct
9 Correct 56 ms 8596 KB Output is correct
10 Correct 75 ms 11104 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 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 30 ms 4872 KB Output is correct
3 Correct 28 ms 4800 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 1876 KB Output is correct
6 Correct 41 ms 6604 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 49 ms 8176 KB Output is correct
9 Correct 56 ms 8596 KB Output is correct
10 Correct 75 ms 11104 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 212 KB Output is correct
14 Correct 76 ms 10604 KB Output is correct
15 Correct 58 ms 7844 KB Output is correct
16 Correct 75 ms 10348 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 75 ms 10860 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 296 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 0 ms 212 KB Output is correct
4 Correct 0 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 1 ms 336 KB Output is correct
8 Correct 0 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 45 ms 6584 KB Output is correct
3 Correct 47 ms 6584 KB Output is correct
4 Correct 76 ms 8684 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 45 ms 6584 KB Output is correct
3 Correct 47 ms 6584 KB Output is correct
4 Correct 76 ms 8684 KB Output is correct
5 Correct 75 ms 9348 KB Output is correct
6 Correct 73 ms 9244 KB Output is correct
7 Correct 88 ms 9532 KB Output is correct
8 Correct 80 ms 9160 KB Output is correct
9 Correct 47 ms 6632 KB Output is correct
10 Correct 71 ms 9016 KB Output is correct
11 Correct 81 ms 8808 KB Output is correct
12 Correct 47 ms 6884 KB Output is correct
13 Correct 46 ms 7380 KB Output is correct
14 Correct 50 ms 7408 KB Output is correct
15 Correct 51 ms 7568 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 51 ms 6400 KB Output is correct
18 Correct 50 ms 6840 KB Output is correct
19 Correct 50 ms 6888 KB Output is correct
20 Correct 70 ms 8960 KB Output is correct
21 Correct 71 ms 8812 KB Output is correct
22 Correct 75 ms 8880 KB Output is correct