Submission #560710

#	Time	Username	Problem	Language	Result	Execution time	Memory
560710		tfg	Mechanical Doll (IOI18_doll)	C++17	84 / 100	135 ms	7676 KiB

doll

#include "doll.h"

const int MAGIC = 1e9;

std::vector<int> X, Y;

int solve(int sz) {
    int id = (int) X.size();
    X.push_back(MAGIC), Y.push_back(MAGIC);
    if(sz == 1) {
        X[id] = -id-1;
    } else if(sz > 2) {
        X[id] = solve(sz/2);
        Y[id] = solve(sz/2);
    }
    return -id-1;
}

int outerSolve(const std::vector<int> &A) {
    int n = (int) A.size();
    if(n == 1) {
        solve(1);
        Y.back() = A.back();
    }
    int id = 0;
    while((1 << id) * 2 <= n) id++;
    for(int i = 0; i <= id; i++) {
        X.push_back(((1 << (id - i)) & n) ? MAGIC : -1), Y.push_back(-(i+1)-1);
    }
    Y.back() = A.back();
    for(int i = 0; i < id; i++) {
        if(X[i] == MAGIC) {
            X[i] = solve(1 << (id - i));
            //std::cout << "tree for 2^" << (id-i) << " in " << X[i] << std::endl;
        }
    }
    std::vector<bool> state(X.size(), false);
    bool wasted = false;
    for(int i = 0; i < (int) X.size(); i++) {
        //std::cout << -(i+1) << ": " << X[i] << ", " << Y[i] << '\n';
    }
    for(auto val : A) {
        int on = -1;
        //std::cout << "val is " << val << std::endl;
        while(on < 0) {
            //std::cout << "on " << on << std::endl;
            //assert(on < 0);
            state[-on-1] = !state[-on-1];
            int &nxt = (state[-on-1] ? X : Y)[-on-1];
            if(nxt == MAGIC && !wasted) {
                nxt = -1;
                wasted = true;
            } else if(nxt >= 0) {
                //assert(nxt == MAGIC || nxt == val);
                nxt = val;
            }
            on = nxt;
        }
        //assert(on == val);
    }
    for(int i = 0; i < (int) X.size(); i++) {
        //assert(!state[i]);
    }
    return -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);
  outerSolve(A);
  answer(C, X, Y);
}

Compilation message (stderr)

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

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