Submission #107321

#	Time	Username	Problem	Language	Result	Execution time	Memory
107321		PeppaPig	Mechanical Doll (IOI18_doll)	C++14	6 / 100	132 ms	16956 KiB

doll

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

using namespace std;

const int N = 2e5+5;

int n, m, idx;
vector<int> g[N], C, X, Y;

void solve(int u, vector<int> &V) {
    if(V.empty()) return void(C[u] = u);
    if((int)V.size() == 1) return void(C[u] = V[0]);

    int L = 0, sz;
    while((1 << L) < (int)V.size()) ++L;
    sz = 1 << L;

    vector<int> add;
    int now = V.size();
    while((int)V.size() < sz) {
        V.emplace_back(idx-1);
        X.emplace_back(--idx), Y.emplace_back(0);
        add.emplace_back(X.size()-1);
    }
    swap(V[now-1], V[V.size()-1]);

    for(int i = 0; i < sz; i++) {
        int pos = 0;
        for(int j = 0; j < L; j++) pos += (i >> j & 1) << (L - j - 1);
        if(i < pos) swap(V[i], V[pos]);
    }

    for(int len = 2; len <= sz; len <<= 1) {
        int half = len >> 1;
        for(int i = 0; i < sz; i += len) {
            int j = i + half;
            if(j > sz) continue;
            X.emplace_back(V[i]), Y.emplace_back(V[j]);
            V[i] = --idx;
        }
    }
    for(int i : add) Y[i] = V[0];
    C[u] = V[0];
}

void create_circuit(int M, vector<int> A) {
    n = A.size(), m = M;
    C.resize(m + 1);

    for(int i = 0; i < n-1; i++) g[A[i]].emplace_back(A[i+1]);
    g[0].emplace_back(A[0]), g[A[n-1]].emplace_back(0);
    for(int i = 0; i <= m; i++) solve(i, g[i]);

    answer(C, X, Y);
}

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