oj.uz

Submission #1041063

# Submission time Handle Problem Language Result Execution time Memory
1041063 2024-08-01T14:38:05 Z NeroZein Mechanical Doll (IOI18_doll) C++17
100 / 100
 79 ms 13108 KB 
#include "doll.h"
#include <bits/stdc++.h>

using namespace std; 

int idd; 
int n, m;
vector<int> a;
vector<int> state;
vector<int> c, x, y;

void build(int nd, int l, int r, int elements) {
  assert(l != r); 
  int mid = (l + r) >> 1;
  int sz = min(elements, r - mid); 
  if (mid + 1 < r) {
    int rx = --idd; 
    x.push_back(0);
    y.push_back(0); 
    y[-nd - 1] = rx; 
    build(rx, mid + 1, r, sz);     
  }
  if (sz == elements) {
    x[-nd - 1] = -1;
  } else if (l < mid) {
    int lx = --idd; 
    x.push_back(0);
    y.push_back(0);
    x[-nd - 1] = lx;
    build(lx, l, mid, elements - sz); 
  }
}

void dfs(int v, int ptr) {
  if (v == 0) {
    return; 
  }
  if (v > 0) {
    dfs(c[v], ptr + 1); 
  } else {
    if (state[-v - 1] == 0) {
      if (!x[-v - 1]) {
        x[-v - 1] = a[ptr]; 
      }
      state[-v - 1] ^= 1; 
      dfs(x[-v - 1], ptr); 
    } else {
      if (!y[-v - 1]) {
        y[-v - 1] = a[ptr];
      }
      state[-v - 1] ^= 1; 
      dfs(y[-v - 1], ptr); 
    }
  }
}

void create_circuit(int m_, vector<int> a_) {
  m = m_; 
  a = a_;
  a.push_back(0);
  n = (int) a.size();
  idd = -1; 
  x.push_back(0);
  y.push_back(0);
  int b = 1; 
  while (b < n) {
    b *= 2; 
  }
  build(-1, 0, b - 1, n);
  c.assign(m + 1, -1); 
  state.resize(-idd); 
  dfs(-1, 0);
  if (-idd > (int) log2(n) + n) {
    assert(n >= 150000); 
  }
  //assert(-idd <= (int) log2(n) + n); 
  answer(c, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 24 ms 5324 KB Output is correct
3 Correct 23 ms 5196 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 1492 KB Output is correct
6 Correct 37 ms 7240 KB Output is correct
7 Correct 0 ms 344 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 24 ms 5324 KB Output is correct
3 Correct 23 ms 5196 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 1492 KB Output is correct
6 Correct 37 ms 7240 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 51 ms 8572 KB Output is correct
9 Correct 66 ms 8936 KB Output is correct
10 Correct 77 ms 13108 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 24 ms 5324 KB Output is correct
3 Correct 23 ms 5196 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 1492 KB Output is correct
6 Correct 37 ms 7240 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 51 ms 8572 KB Output is correct
9 Correct 66 ms 8936 KB Output is correct
10 Correct 77 ms 13108 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 77 ms 12556 KB Output is correct
15 Correct 53 ms 8056 KB Output is correct
16 Correct 79 ms 12340 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 76 ms 12804 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 45 ms 6520 KB Output is correct
3 Correct 45 ms 6776 KB Output is correct
4 Correct 66 ms 10036 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 45 ms 6520 KB Output is correct
3 Correct 45 ms 6776 KB Output is correct
4 Correct 66 ms 10036 KB Output is correct
5 Correct 75 ms 11572 KB Output is correct
6 Correct 75 ms 11400 KB Output is correct
7 Correct 74 ms 11316 KB Output is correct
8 Correct 73 ms 11156 KB Output is correct
9 Correct 43 ms 7028 KB Output is correct
10 Correct 69 ms 11072 KB Output is correct
11 Correct 69 ms 10548 KB Output is correct
12 Correct 47 ms 7032 KB Output is correct
13 Correct 47 ms 7556 KB Output is correct
14 Correct 49 ms 7544 KB Output is correct
15 Correct 51 ms 7744 KB Output is correct
16 Correct 1 ms 856 KB Output is correct
17 Correct 44 ms 7504 KB Output is correct
18 Correct 43 ms 7024 KB Output is correct
19 Correct 44 ms 7032 KB Output is correct
20 Correct 73 ms 10804 KB Output is correct
21 Correct 68 ms 10544 KB Output is correct
22 Correct 67 ms 10544 KB Output is correct