Submission #1244850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244850		j_vdd16	Mechanical Doll (IOI18_doll)	C++20	9 / 100	52 ms	8132 KiB

doll

#include <iostream>
#include <vector>
#include <queue>

#include "doll.h"

using namespace std;

#define loop(X, N) for (int X = 0; X < (N); X++)

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;

int rev(int n, int numBits) {
    int out = 0;
    for (int i = 0; i < numBits; i++) {
        if (n & (1 << i))
            out |= 1 << (numBits - 1 - i);
    }

    return out;
}

void create_circuit(int m, vi a) {
    vi c; //exits
    vi x, y;

    int n = a.size();
    c.push_back(a[0]);
    
    int pow = 1;
    int numBits = 0;
    while (pow < n) {
        numBits++;
        pow *= 2;
    }

    if (pow > 1) {
        vi exits(pow);
        for (int j = 0; j < n - 1; j++) {
            exits[rev(j, numBits)] = a[j + 1];
        }
        for (int j = n - 1; j < pow - 1; j++) {
            exits[rev(j, numBits)] = -1;
        }
        exits[rev(pow - 1, numBits)] = 0;

        for (int j = 1; j < pow / 2; j++) {
            x.push_back(-2 * j);
            y.push_back(-2 * j - 1);
        }
        for (int j = 0; j < pow / 2; j++) {
            x.push_back(exits[j * 2]);
            y.push_back(exits[j * 2 + 1]);
        }

        c.push_back(-1);
    }
    
    answer(c, x, y);
}

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