제출 #154800

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
154800		darkkcyan	자동 인형 (IOI18_doll)	C++14	84 / 100	178 ms	8412 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);
    while (len(groups) > 1) {
        vector<int> new_groups;
        if (len(groups) & 1) {
            new_groups.push_back(~len(x));
            x.push_back(INT_MIN);
            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);
    for (auto& i: x) if (i == INT_MIN) i = root;

    std::vector<int> c(m + 1, root);
    c[0] = a[0];
    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];
    }
    answer(c, x, y);
}

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