Submission #1244740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244740		joenpoenmanalt	Mechanical Doll (IOI18_doll)	C++20	53 / 100	71 ms	14632 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

#define ALL(x) begin(x), end(x)

int rev_bin(int x, int bits) {
    int r = 0;
    for (int k = 0; k < bits; k++) {
        if (x & (1<<k)) r += (1<<(bits-k-1));
    }
    return r;
}


void create_circuit(int M, std::vector<int> A)
{
    int N = A.size();
    A.push_back(0);
    std::vector<int> C(M + 1);
    std::vector<int> X, Y;
    int idx = -1;
    
    vvi out(M+1);
    for (int i = 0; i < N; i++) out[A[i]].push_back(A[i+1]);

    C[0] = A[0];
    for (int i = 1; i <= M; i++) {
        if (out[i].size() == 0) C[i] = i;
        else if (out[i].size() == 1) C[i] = out[i][0];
        else {
            C[i] = idx;
            int k = 0;
            while ((1<<k) < out[i].size()) k++;
            reverse(ALL(out[i]));
            while (out[i].size() < (1<<k)) out[i].push_back(idx);
            reverse(ALL(out[i]));
            vi ass(2<<k);
            for (int i = 1; i < (1<<k); i++) {
                ass[i] = (idx--);
            }
            assert((1<<k) == out[i].size());
            for (int j = 0; j < (1<<k); j++) ass[(1<<k) + rev_bin(j, k)] = out[i][j];
            for (int i = 1; i < (1<<k); i++) {
                X.push_back(ass[2*i]);
                Y.push_back(ass[2*i+1]);
            }
        }
    }


    // cerr << "DEBUG INFO:\n";
    // for (int x : C) cerr << x << ' '; cerr << '\n';
    // for (int x : X) cerr << x << ' '; cerr << '\n';
    // for (int x : Y) cerr << x << ' '; cerr << '\n';
    answer(C, X, Y);
}

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