제출 #221647

#제출 시각아이디문제언어결과실행 시간메모리
221647galca자동 인형 (IOI18_doll)C++14
54.38 / 100
130 ms8656 KiB
#include "doll.h" #include <vector> #include <iostream> using namespace std; // N + 1 = 15 // num_bits = 4 // we should have: 1 + 2 + 4 + 8 void create_circuit(int M, std::vector<int> A) { int N = A.size(); std::vector<int> C(M + 1); for (int i = 0; i <= M; ++i) { C[i] = -1; } std::vector<int> X, Y; // compute depth and number of elements in each tree + remaining counter int num_bits = 0; int tmp = N; while (tmp > 0) { ++num_bits; tmp >>= 1; } vector<int> trees; int current_tree = 1 << (num_bits - 1); // for N = 16, this is 16 int sum_of_trees = 0; while (sum_of_trees < N) { trees.push_back(current_tree); sum_of_trees += current_tree; current_tree >>= 1; } int tail_counter = trees[trees.size() - 1]; //cout << " the tail will be " << tail_counter << endl; // create the trees // all triggers belong to the trees // the counter eventually lead to exit int idx = 1; int el_idx = 0; vector<int> order; int n_trees = trees.size(); int mask = 0; // 0 1 2 - 4 5 6 - // 0 1 2 3 4 5 6 - // int counter_pos = 1 << n_trees; for (int i = 0; i < (1 << num_bits); i++) { if ((i % counter_pos) == (counter_pos-1)) { order.push_back(-1); } else { order.push_back(el_idx++); } } // factor: 2, 4, 8, ... // offset: 0, 1, 3, // tree i : elements 0 modulo 1<<(i+1) + i*2+1 for (int i = 0; i < trees.size(); i++) { int current_size = trees[i]; int tree_factor = 1 << (i + 1); int tree_offset = (tree_factor >> 1) - 1; // add the root X.push_back(-(idx+1)); Y.push_back(-(idx + current_size)); // the tree itself int my_idx = 1; int start_idx = idx; for (int k = 1; (1 << (k - 1)) < current_size; ++k) { int n_nodes = 1 << (k - 1); //cout << "creating " << n_nodes << " for the tree of " << current_size << endl; for (int n = 1; n <= n_nodes; n++) { X.push_back(-(start_idx + my_idx * 2)); Y.push_back(-(start_idx + my_idx * 2 + 1)); my_idx++; } } //cout << "overall in the tree of " << current_size << " created " << my_idx << " nodes " << endl; // replace last level with triggers int n_nodes = current_size >> 1; int idx_b = n_nodes != 0 ? (X.size() - n_nodes) : (X.size() - 1); for (int n = 0; n < current_size; n++) { // revert the number int offset = n_nodes; int n_tmp = n; int n_pos = 0; while (n_tmp > 0) { if (n_tmp & 1) { n_pos += offset; } n_tmp >>= 1; offset >>= 1; } if (n_pos & 1) { int key = order[n*tree_factor + tree_offset]; if (key < N) { Y[idx_b + n_pos / 2] = A[key]; } else { Y[idx_b + n_pos / 2] = -1; } //cout << "connecting trigger at pos " << key << " val " << A[key] << " to Y at " << n_pos / 2 << endl; //cout << "idx in Y " << idx_b + n_pos / 2 << endl; } else { int key = order[n*tree_factor + tree_offset]; if (key < N) { X[idx_b + n_pos / 2] = A[key]; } else { X[idx_b + n_pos / 2] = -1; } //cout << "connecting trigger at pos " << key << " val " << A[key] << " to X at " << n_pos / 2 << endl; //cout << "idx in X " << idx_b + n_pos / 2 << endl; } } idx += current_size; tree_offset = tree_offset * 2 + 1; tree_factor *= 2; } #if 0 cout << "arrays so far " << endl; for (int i = 0; i < X.size(); i++) { cout << X[i] << " "; } cout << endl; for (int i = 0; i < Y.size(); i++) { cout << Y[i] << " "; } cout << endl; #endif // add the counter tail_counter >>= 1; while (tail_counter > 0) { X.push_back(-1); Y.push_back(-(idx+1)); ++idx; tail_counter >>= 1; } Y[Y.size() - 1] = 0; #if 0 cout << "arrays with the tail counter " << endl; for (int i = 0; i < X.size(); i++) { cout << X[i] << " "; } cout << endl; for (int i = 0; i < Y.size(); i++) { cout << Y[i] << " "; } cout << endl; #endif #if 0 for (int n = 0; n < N; n++) { // revert the number int offset = n_leaves; int n_tmp = n; int n_pos = 0; while (n_tmp > 0) { if (n_tmp & 1) { n_pos += offset; } n_tmp >>= 1; offset >>= 1; } if (n_pos & 1) { Y[idx_b + n_pos/2] = A[n]; //cout << "connecting trigger " << n << " to Y at " << n_pos / 2 << endl; } else { X[idx_b + n_pos/2] = A[n]; //cout << "connecting trigger " << n << " to X at " << n_pos / 2 << endl; } } #endif answer(C, X, Y); }

컴파일 시 표준 에러 (stderr) 메시지

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:67:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for (int i = 0; i < trees.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~
doll.cpp:49:6: warning: unused variable 'mask' [-Wunused-variable]
   49 |  int mask = 0;
      |      ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...