Submission #609498

#	Time	Username	Problem	Language	Result	Execution time	Memory
609498		lorenzoferrari	Bit Shift Registers (IOI21_registers)	C++17	10 / 100	1 ms	628 KiB

registers

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

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

int st = M - 1;

struct id {
    int i;
    id() : i(st--) {}
    ~id() { ++st; }
};

int n, k;
int id_zero = st--;
int id_one = st--;
vector<bool> zero(B);
vector<bool> one(B);

// if (r[a] is NULL) r[t] is set to 0
// else r[t] is set to 1
void MAKEBOOL(int t, int a) {
    append_move(t, a);
    id shifted;
    for (int i = 1; i < k; i <<= 1) {
        append_left(shifted.i, t, i);
        append_or(t, t, shifted.i);
        // append_right(shifted.i, t, i);
        // append_or(t, t, shifted.i);
    }
    append_left(shifted.i, t, k / 2);
    append_or(t, t, shifted.i);
    // append_right(shifted.i, t, B / 2);
    // append_or(t, t, shifted.i);
    
    // DEBUG
    // append_print(a);
    // append_print(t);
}

// if (r[x] is NULL) r[t] = r[b]
// else r[t] = r[a]
void TERNARY(int t, int a, int b, int x) { // (t, if_true, if_false, bool)
    assert(a != b);
    id mask, f1, f2;
    MAKEBOOL(mask.i, x);
    append_and(f1.i, mask.i, a);
    append_not(mask.i, mask.i);
    append_and(f2.i, mask.i, b);
    append_add(t, f1.i, f2.i);
}

void EXTRACT_SUBSEGMENT(int t, int a, int l, int r) {
    append_move(t, a);
    append_left(t, t, B-1-r);
    append_right(t, t, B-1-r+l);
}

void GET_BIT(int t, int a, int i) {
    EXTRACT_SUBSEGMENT(t, a, i, i);
}

// r[t] becomes bool(a < b)
void LESS(int t, int a, int b) {
    assert(a != b);
    append_move(t, id_zero);
    id oa, ob;
    append_move(oa.i, a);
    append_move(ob.i, b);
    id ta, tb;
    for (int i = k-1; i >= 0; --i) {
        GET_BIT(ta.i, oa.i, i);
        GET_BIT(tb.i, ob.i, i);

        // if r[a][0] & !r[b][0]:
        //     set r[a] to 0 else r[a]
        //     set ans to 0 else ans
        //
        // ... same con r[b][0] & !r[a]

        id tnot, tand;
        append_not(tnot.i, ta.i);
        append_and(tand.i, tnot.i, tb.i);
        TERNARY(t, id_one, t, tand.i);
        TERNARY(oa.i, id_zero, oa.i, tand.i);

        append_not(tnot.i, tb.i);
        append_and(tand.i, ta.i, tnot.i);
        TERNARY(t, id_zero, t, tand.i);
        TERNARY(ob.i, id_zero, ob.i, tand.i);
    }
}

// r[t] becomes the i-th integer in r[0]
void GET_INPUT(int t, int i) {
    EXTRACT_SUBSEGMENT(t, 0, k*i, k*i+k-1);
}

// r[t] stores min(r[a], r[b])
void MIN(int t, int a, int b) {
    id comp;
    LESS(comp.i, a, b);
    TERNARY(t, a, b, comp.i);
}

void construct_instructions(int s, int n, int k, int q) {
    ::n = n, ::k = k;
    assert(s == 0); // find minimum
    for (int i = 0; i < B; ++i) { one[i] = 1; }
    append_store(id_one, one);
    append_store(id_zero, zero);

    // actual code
    id ans;
    append_move(ans.i, id_one);
    for (int i = 0; i < n; ++i) {
        id cur;
        GET_INPUT(cur.i, i);
        MIN(ans.i, ans.i, cur.i);
    }
    append_move(0, ans.i);
}

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