Submission #1197284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197284		totoro	Bit Shift Registers (IOI21_registers)	C++20	10 / 100	1 ms	580 KiB

registers

#include "registers.h"

#define append_print(x) 42

#include <iostream>
#include <set>

const int b = 2000;

struct Allocator {
    std::set<int> available;
    void init() {
        for (int i = 0; i < b; ++i) available.insert(i);
    }
    void free(int i) {
        available.insert(i);
    }
    int create() {
        if (available.empty()) {
            std::cout << "ALLOCATOR: FAILED TO ALLOCATE: NOT ENOUGH FREE SPACE" << std::endl;
            exit(1);
        }
        int i = *available.begin();
        available.erase(available.begin());
        return i;
    }
};

void construct_instructions(int s, int n, int k, int q) {
    std::vector<bool> buf(b);

    auto clearbuf = [&buf]() {
        buf.assign(b, 0);
    };

    Allocator alloc;
    alloc.init();
    int ans = alloc.create();

    /* PREPARE CONSTANTS */
    int ONE = alloc.create();
    clearbuf();
    buf[0] = 1;
    append_store(ONE, buf);

    /* READ INPUT */
    std::vector<int> vals(n);
    for (int& i : vals) i = alloc.create();

    int inputReadingMsk = alloc.create();
    clearbuf();
    for (int i = 0; i < k; ++i) buf[i] = 1;
    append_store(inputReadingMsk, buf);
    for (int i = 0; i < n; ++i) {
        append_and(vals[i], 0, inputReadingMsk);
        append_right(0, 0, k);
    }

    for (int i = 0; i < n; ++i) {
        append_print(vals[i]);
    }

    alloc.free(inputReadingMsk);

    /* CONSTRUCT ANS */
    int curbitMsk = alloc.create();
    clearbuf();
    buf[k] = 1;
    append_store(curbitMsk, buf);

    for (int bit = k - 1; bit >= 0; --bit) {
        append_right(curbitMsk, curbitMsk, 1);
        int aux = alloc.create();
        append_move(aux, curbitMsk);
        for (int i = 0; i < n; ++i) {
            append_and(aux, aux, vals[i]);
        }
        append_or(ans, ans, aux);
        append_xor(aux, aux, curbitMsk);  // flips the current bit
        for (int i = 0; i < n; ++i) {
            int thisFlag = alloc.create();
            append_and(thisFlag, vals[i], aux);
            append_right(thisFlag, thisFlag, bit);
            append_not(thisFlag, thisFlag);
            append_add(thisFlag, thisFlag, ONE);
            append_or(vals[i], vals[i], thisFlag);
            alloc.free(thisFlag);
        }

        alloc.free(aux);
    }
}

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