Submission #560693

#	Time	Username	Problem	Language	Result	Execution time	Memory
560693		tfg	Mechanical Doll (IOI18_doll)	C++17	47 / 100	145 ms	13824 KiB

doll

#include "doll.h"

std::vector<int> X, Y;

int solve(std::vector<int> A) {
    int id = (int) X.size();
    X.push_back(-id-1), Y.push_back(-id-1);
    int n = (int) A.size();
    if(n == 1) {
        Y[id] = A[0];
    } else if(n == 2) {
        X[id] = A[0];
        Y[id] = A[1];
    } else {
        if(n % 2) {
            n++;
            A.insert(A.end() - 1, -id-1);
        }
        std::vector<int> parts[2];
        for(int i = 0; i < n; i++) {
            parts[i%2].push_back(A[i]);
        }
        X[id] = solve(parts[0]);
        Y[id] = solve(parts[1]);
    }
    return -id-1;
}

void create_circuit(int M, std::vector<int> A) {
  int N = A.size();
  std::vector<int> C(M + 1, -1);
  C[0] = A[0];
  A.erase(A.begin());
  A.push_back(0);
  solve(A);
  answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:30:7: warning: unused variable 'N' [-Wunused-variable]
   30 |   int N = A.size();
      |       ^

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 9.0000000036 / 18
• Subtask 6: 28.0000000112 / 56