Submission #1210958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210958		Hggf	Mechanical Doll (IOI18_doll)	C++20	65.67 / 100	216 ms	38488 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,avx2,bmi,bmi2,lzcnt,popcnt,sse,sse2,sse3,sse4")
using namespace std;
int sz = 0;
map<int, int>xx, yy;
void gen(int v, vector<int>sns, int pr = 1) {
    // cout << v << endl;
    // for (auto u : sns) {
    //     cout << u << ' ';
    // }
    // cout << endl;
    if (sns[0] == sns.back() && sns[0] == 6999999) {
        xx[v] = pr;
        yy[v] = pr;
        return;
    }
    // cout << v << ':' << " ";
    // for (auto u : sns) {
    //     cout << u << ' ';
    // }
    // cout << endl;
    if (sns.size() == 2) {
        if (sns[0] == 6999999) {
            xx[v] = pr;
        } else {
            xx[v] = sns[0];
        }
        if (sns[1] == 6999999) {
            yy[v] = pr;
        } else {
            yy[v] = sns[1];
        }
        return;
    }
    vector<int>v1, v2;
    for (int i = 0; i < sns.size(); i++) {
        if (i & 1) {
            v2.push_back(sns[i]);
        } else {
            v1.push_back(sns[i]);
        }
    }
    if (pr > 0) {
        pr = v;
    }
    xx[v] = sz - 1;
    gen(--sz, v1, pr);
    yy[v] = sz - 1;
    gen(--sz, v2, pr);
}
void create_circuit(int M, vector<int>A) {
    vector<int>G[M + 1];
    A.insert(A.begin(), 0);
    for (int i = 0; i < A.size(); i++) {
        G[A[i]].push_back(A[(i + 1) % A.size()]);
    }
    vector<int> to(M + 1);
    for (int i = 0; i <= M; i++) {
        if (G[i].size() == 1) {
            to[i] = G[i][0];
        } else if (G[i].size()) {
            sz--;
            to[i] = sz;
            int tot = 2;
            while (tot < G[i].size()) {
                tot *= 2;
            }
            vector<int>P;
            for (int i = 0; i < tot; i++) {
                P.push_back(i);
            }
            for (int j = 20; j >= 0; j--) {
                if ((1 << j) > P.size()) {
                    continue;
                }
                vector<int>np;
                for (int t = 0; t < P.size(); t += 2 * (1 << j)) {
                    for (int l = t; l < t + (1 << j); l++) {
                        np.push_back(P[l]);
                    }
                }
                for (int t = (1 << j); t < P.size(); t += 2 * (1 << j)) {
                    for (int l = t; l < t + (1 << j); l++) {
                        np.push_back(P[l]);
                    }
                }
                P = np;
            }
            vector<int>RG(tot, -1);
            // cout << tot << ' ' << G[i].size() << endl;
            int st = 0;
            for (int j = st; j < st + tot - G[i].size(); j++) {
                RG[P[j]] = 6999999;
            }
            reverse(G[i].begin(), G[i].end());
            for (int j = 0; j < tot; j++) {
                if (RG[j] < 0) {
                    RG[j] = G[i].back();
                    G[i].pop_back();
                }
            }
            G[i] = RG;
            vector<int>neg = {};
            gen(sz, G[i]);
        } else {
            to[i] = 0;
        }
    }
    vector<int>X, Y;
    for (int i = 1; i <= -sz; i++) {
        X.push_back(xx[-i]);
        Y.push_back(yy[-i]);
        // cout << i << ' ' << X.back() << ' ' << Y.back() << endl;
    }
    assert(X.size() <= 2 * A.size());
    answer(to, X, Y);
}

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