Submission #607898

#	Time	Username	Problem	Language	Result	Execution time	Memory
607898		KoD	Bit Shift Registers (IOI21_registers)	C++17	100 / 100	1 ms	468 KiB

registers

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

using std::array;
using std::pair;
using std::tuple;
using std::vector;

constexpr int M = 100;
constexpr int B = 2000;

namespace ops {

bool locked[B];
bool vacant[B];

void init() {
    locked[0] = true;
    for (int i = 1; i < M; ++i) {
        vacant[i] = true;
    }
}

void lock(const int r) {
    assert(!locked[r]);
    assert(!vacant[r]);
    locked[r] = true;
}

void dump(const int r) {
    assert(!locked[r]);
    assert(!vacant[r]);
    vacant[r] = true;
}

void dump_all() {
    for (int i = 0; i < M; ++i) {
        if (!locked[i] and !vacant[i]) {
            dump(i);
        }
    }
}

int get_free() {
    int r = 0;
    while (r < M and !vacant[r]) {
        r += 1;
    }
    assert(r != M);
    vacant[r] = false;
    return r;
}

int copy(const int from) {
    assert(0 <= from and from < M);
    const int t = get_free();
    append_move(t, from);
    return t;
}

void debug(const int x) {
    assert(0 <= x and x < M);
    append_print(x);
}

void copy_to(const int from, const int to) {
    assert(0 <= from and from < M);
    assert(0 <= to and to < M);
    append_move(to, from);
}

int create(const vector<bool>& v) {
    assert((int)v.size() == B);
    const int t = get_free();
    append_store(t, v);
    return t;
}

int AND(const int x, const int y) {
    assert(0 <= x and x < M);
    assert(0 <= y and y < M);
    const int t = get_free();
    append_and(t, x, y);
    return t;
}

int OR(const int x, const int y) {
    assert(0 <= x and x < M);
    assert(0 <= y and y < M);
    const int t = get_free();
    append_or(t, x, y);
    return t;
}

int XOR(const int x, const int y) {
    assert(0 <= x and x < M);
    assert(0 <= y and y < M);
    const int t = get_free();
    append_xor(t, x, y);
    return t;
}

int ADD(const int x, const int y) {
    assert(0 <= x and x < M);
    assert(0 <= y and y < M);
    const int t = get_free();
    append_add(t, x, y);
    return t;
}

int NOT(const int x) {
    assert(0 <= x and x < M);
    const int t = get_free();
    append_not(t, x);
    return t;
}

int LEFT(const int x, const int s) {
    assert(0 <= x and x < M);
    assert(0 <= s and s <= B);
    const int t = get_free();
    append_left(t, x, s);
    return t;
}

int RIGHT(const int x, const int s) {
    assert(0 <= x and x < M);
    assert(0 <= s and s <= B);
    const int t = get_free();
    append_right(t, x, s);
    return t;
}

}

void solve_minimum(const int N, const int K) {
    for (int d = 1; d < N; d *= 2) {
        vector<bool> X(B), Y(B), Z(B, true);
        for (int i = 0; i + d < N; i += 2 * d) {
            for (int j = i * K; j < (i + 1) * K; ++j) {
                X[j] = true;
                Y[j + d * K] = true;
                Z[j] = false;
                Z[j + d * K] = false;
            }
        }
        const int x = ops::AND(ops::create(X), 0);
        const int y = ops::RIGHT(ops::AND(ops::create(Y), 0), d * K);
        const int sum = ops::ADD(ops::NOT(x), y);
        const int swap = ops::RIGHT(sum, K);
        const int stay = ops::NOT(swap);
        const int small = ops::OR(ops::AND(swap, y), ops::AND(stay, x));
        const int large = ops::OR(ops::AND(swap, x), ops::AND(stay, y));
        if (N == 2) {
            ops::copy_to(ops::OR(small, ops::LEFT(large, d * K)), 0);
        } else {
            ops::copy_to(ops::OR(ops::OR(small, ops::LEFT(large, d * K)), ops::AND(0, ops::create(Z))), 0);
        }
        ops::dump_all();
    }
}

void solve_sort(const int N, const int K) {
    array<int, 2> x, y, z;
    for (int k = 0; k < 2; ++k) {
        vector<bool> X(B), Y(B), Z(B, true);
        for (int i = k; i + 1 < N; i += 2) {
            for (int j = i * K; j < (i + 1) * K; ++j) {
                X[j] = true;
                Y[j + K] = true;
                Z[j] = false;
                Z[j + K] = false;
            }
        }
        x[k] = ops::create(X);
        y[k] = ops::create(Y);
        z[k] = ops::create(Z);
        ops::lock(x[k]);
        ops::lock(y[k]);
        ops::lock(z[k]);
    }
    for (int step = 0; step < N; ++step) {
        const int k = step % 2;
        const int p = ops::AND(x[k], 0);
        const int q = ops::RIGHT(ops::AND(y[k], 0), K);
        const int sum = ops::ADD(ops::NOT(p), q);
        const int swap = ops::RIGHT(sum, K);
        const int stay = ops::NOT(swap);
        const int small = ops::OR(ops::AND(swap, q), ops::AND(stay, p));
        const int large = ops::OR(ops::AND(swap, p), ops::AND(stay, q));
        ops::copy_to(ops::OR(ops::OR(small, ops::LEFT(large, K)), ops::AND(0, z[k])), 0);
        ops::dump_all();
    }
}

void construct_instructions(int Subtask, int N, int K, int) {
    ops::init();
    if (Subtask == 0) {
        solve_minimum(N, K);
    } else {
        solve_sort(N, K);
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 25 / 25
• Subtask 5: 13 / 13
• Subtask 6: 29 / 29