Submission #154806

#	Time	Username	Problem	Language	Result	Execution time	Memory
154806		darkkcyan	Mechanical Doll (IOI18_doll)	C++14	100 / 100	162 ms	8768 KiB

doll

/**
 * Author: Tran Quang Loc
 * Tue Sep 24 15:50:15 MSK 2019
 */

#include<bits/stdc++.h>
#include "doll.h"

using namespace std;
using namespace std::placeholders;

#define llong long long 
#define xx first
#define yy second
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#define all(x) x.begin(), x.end()
// #define rand __rand
// mt19937 rng(chrono::system_clock::now().time_since_epoch().count());  // or mt19937_64
// template<class T = int> T rand(T range = numeric_limits<T>::max()) {
    // return (T)(rng() % range);
// }

void create_circuit(int m, std::vector<int> a) {
    int n = len(a);
    vector<int> x, y;
    vector<int> groups(n, 0);
    int fake_root = INT_MIN;
    while (len(groups) > 1) {
        vector<int> new_groups;
        if (len(groups) & 1) {
            new_groups.push_back(~len(x));
            x.push_back(fake_root);
            y.push_back(groups[0]);
        }
        for (int i = len(groups) & 1; i + 1 < len(groups); i += 2) {
            new_groups.push_back(~len(x));
            x.push_back(groups[i]);
            y.push_back(groups[i + 1]);
        }
        swap(groups, new_groups);
    }
    
    int root = ~(len(x) - 1);
    replace(x.begin(), x.end(), fake_root, root);

    std::vector<int> c(m + 1, root);
    c[0] = a[0];
    if (n > 1) { 
        a.erase(a.begin(), a.begin() + 1);
        a.push_back(0);
        vector<int> states(len(x));
        rep(i, n) {
            int cur = ~(len(x) - 1), prev = cur;
            while (cur < 0) {
                prev = cur;
                cur = states[~cur] ? y[~cur] : x[~cur];
                states[~prev] ^= 1;
            }
            (states[~prev] ? x[~prev] : y[~prev]) = a[i];
        }
    } else {
        c[a[0]] = 0;
    }
    answer(c, x, y);
}

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