Submission #109440

#	Time	Username	Problem	Language	Result	Execution time	Memory
109440		nvmdava	Mechanical Doll (IOI18_doll)	C++17	100 / 100	173 ms	11116 KiB

doll

//#include "doll.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
vector<int> C, X, Y, st;
int sz = 0;

void create_circuit(int M, std::vector<int> A);

void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);

void solve(int id, int cnt, int dep){
    dep--;
    if(dep == 0){
        if(cnt == 1){
            X[-1-id] = -1;
            Y[-1-id] = 0;
        } else {
            X[-1-id] = 0;
            Y[-1-id] = 0;
        }
        return;
    }
    int l, r;
    r = min(1 << dep, cnt);
    l = cnt - r;
    X[-1-id] = -1;
    Y[-1-id] = -1;
    if(r){
        X.pb(0);
        Y.pb(0);
        st.pb(0);
        Y[-1-id] = --sz;
    }
    if(l){
        X.pb(0);
        Y.pb(0);
        st.pb(0);
        X[-1-id] = --sz;
    }
    if(r) solve(Y[-1-id], r, dep);
    if(l) solve(X[-1-id], l, dep);
}

void trav(int id, vector<int>& v, int t){
//    cerr<<id<<'\n';
    if(st[-1-id] == 0){
        st[-1-id] = 1;
        if(X[-1-id] == 0){
            X[-1-id] = v[t++];
            if(t == v.size()) return;
            trav(-1, v, t);
        } else
            trav(X[-1-id], v, t);
    } else {
        st[-1-id] = 0;
        if(Y[-1-id] == 0){
            Y[-1-id] = v[t++];
            if(t == v.size()) return;
            trav(-1, v, t);
        } else {
            trav(Y[-1-id], v, t);
        }
    }
}

void create_circuit(int M, vector<int> A) {
	C.resize(M + 1);
	--sz;
    for(int& x : C)
        x = -1;
    X.pb(0);
    Y.pb(0);
    st.pb(0);
    A.pb(0);
    solve(-1, A.size(), ceil(log2(A.size())));
    trav(-1, A, 0);
	answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void trav(int, std::vector<int>&, int)':
doll.cpp:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             if(t == v.size()) return;
      |                ~~^~~~~~~~~~~
doll.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             if(t == v.size()) return;
      |                ~~^~~~~~~~~~~

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