oj.uz

Submission #475994

# Submission time Handle Problem Language Result Execution time Memory
475994 2021-09-24T14:49:45 Z kessido Mechanical Doll (IOI18_doll) C++17
100 / 100
 116 ms 11040 KB 
#include "doll.h"
#include <bits/stdc++.h>
const int UNASSINED = 1'000'000'000;
const int ROOT = 1'000'000'001;
 
using vi = std::vector<int>;

template<typename T>
void print_array(std::string name, const T& array) {
  std::cout << name << "[Array]:\n";
  for(auto &i : array) std::cout << i << " ";
  std::cout << '\n';
}

vi create_level(const vi& last_level, vi& X, vi& Y, int& S) {
  vi new_level;
  for(size_t i = 0; i < last_level.size(); i+=2) {
    if(i+1 < last_level.size()) {
      X.push_back(last_level[i]);
      Y.push_back(last_level[i+1]);
    } else {
      X.push_back(ROOT);
      Y.push_back(last_level[i]);
    }
    new_level.push_back(-1 * (++S));
  }
  return new_level;
}
 
int& simulate_untill_next_unassined(int cur_switch, vi& state, vi& X, vi& Y) {
  while(true) {
    int idx = -cur_switch - 1;
    int* ptr = state[idx] ? &Y[idx] : &X[idx];
    state[idx] ^= 1;
    int& val = *ptr;
    if(val == UNASSINED) return val;
    assert(val < 0);
    cur_switch = val;
  }
}
 
void create_circuit(int M, std::vector<int> A) {
  const int N = A.size();
  // create tree with N leefs
  vi X, Y;
  vi last_level(N, UNASSINED);
  int S = 0;
  do { 
    last_level = create_level(last_level, X, Y, S);
  } while(last_level.size() != 1);
  
  int root = -S;
  assert(last_level.back() == root);
  for(int i = 0; i < S; i++)
    if(X[i]==ROOT)
      X[i] = root;
 
  vi C(M + 1, root);
  C[0] = A[0]; // first go to A0, and than everyone goes to root.
  vi state(S);
  for(int i = 1; i < N; i++) {
    int& v = simulate_untill_next_unassined(root, state, X, Y);
    v = A[i];
  }
  int& last_v = simulate_untill_next_unassined(root, state, X, Y);
  last_v = 0;
  for(int i : state) assert(i == 0);
  for(int i : X) assert(i != UNASSINED);
  for(int i : Y) assert(i != UNASSINED);
  assert(int(X.size()) == S);
  assert(int(Y.size()) == S);
  answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 45 ms 4392 KB Output is correct
3 Correct 39 ms 3876 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 11 ms 1356 KB Output is correct
6 Correct 57 ms 5820 KB Output is correct
7 Correct 0 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 45 ms 4392 KB Output is correct
3 Correct 39 ms 3876 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 11 ms 1356 KB Output is correct
6 Correct 57 ms 5820 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 75 ms 8296 KB Output is correct
9 Correct 84 ms 7964 KB Output is correct
10 Correct 116 ms 11040 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 45 ms 4392 KB Output is correct
3 Correct 39 ms 3876 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 11 ms 1356 KB Output is correct
6 Correct 57 ms 5820 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 75 ms 8296 KB Output is correct
9 Correct 84 ms 7964 KB Output is correct
10 Correct 116 ms 11040 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 110 ms 10372 KB Output is correct
15 Correct 72 ms 6632 KB Output is correct
16 Correct 116 ms 10048 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 116 ms 10664 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 0 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 67 ms 5544 KB Output is correct
3 Correct 69 ms 4808 KB Output is correct
4 Correct 99 ms 7308 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 67 ms 5544 KB Output is correct
3 Correct 69 ms 4808 KB Output is correct
4 Correct 99 ms 7308 KB Output is correct
5 Correct 114 ms 8412 KB Output is correct
6 Correct 108 ms 8016 KB Output is correct
7 Correct 104 ms 8116 KB Output is correct
8 Correct 103 ms 7724 KB Output is correct
9 Correct 71 ms 4856 KB Output is correct
10 Correct 102 ms 7644 KB Output is correct
11 Correct 99 ms 7308 KB Output is correct
12 Correct 66 ms 5080 KB Output is correct
13 Correct 67 ms 6244 KB Output is correct
14 Correct 71 ms 5276 KB Output is correct
15 Correct 69 ms 5520 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 61 ms 5812 KB Output is correct
18 Correct 64 ms 5776 KB Output is correct
19 Correct 67 ms 4812 KB Output is correct
20 Correct 105 ms 7376 KB Output is correct
21 Correct 99 ms 7316 KB Output is correct
22 Correct 103 ms 7316 KB Output is correct