Submission #154774

#	Time	Username	Problem	Language	Result	Execution time	Memory
154774		rama_pang	Mechanical Doll (IOI18_doll)	C++14	100 / 100	191 ms	12896 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> state, L, R;
int id = 0, S = 0;

int build(int node, int triggers) {
    if (triggers == 0) return -1;
    if (node == 1) return id++;
    int now = - (++S);
    L[-now] = build(node / 2, triggers - min(node / 2, triggers));
    R[-now] = build(node / 2, min(node / 2, triggers));
    return now;
}

int dfs(int n) {
    if (n >= 0) return n;
    state[-n] ^= 1;
    if (state[-n] == 1) 
        return dfs(L[-n]);
    else 
        return dfs(R[-n]);
}

void create_circuit(int M, vector<int> A) {
    A.push_back(0);
    int k = 1; while (k < A.size()) k *= 2;
    L.resize(k ), R.resize(k), state.resize(k);
    build(k, A.size());
    vector<int> C(M + 1, -1), dest(id + id), X(S), Y(S);
    for (int i = 0; i < A.size(); i++) dest[dfs(-1)] = A[i];
    for (int i = 1; i <= S; i++) {
        X[i - 1] = L[i], Y[i - 1] = R[i];
        if (0 <= X[i - 1]) X[i - 1] = dest[X[i - 1]];
        if (0 <= Y[i - 1]) Y[i - 1] = dest[Y[i - 1]];
    }
    answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:28:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     int k = 1; while (k < A.size()) k *= 2;
      |                       ~~^~~~~~~~~~
doll.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < A.size(); i++) dest[dfs(-1)] = A[i];
      |                     ~~^~~~~~~~~~

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