Submission #609461

#	Time	Username	Problem	Language	Result	Execution time	Memory
609461		lorenzoferrari	Bit Shift Registers (IOI21_registers)	C++17	0 / 100	2 ms	588 KiB

registers

/*
 * NOTES
 *
 * - posso fare una funzione AND/OR per fare l'AND/OR di tutti i bit di un registro
 *      (ANDify, ORify)
 * - posso costruire il ternario:
 *      // t = a if x, b otherwise
 *      CHOOSE(t, a, b, x): // t : final register, a b : fattori, x = bool
 *          ORify(i = st--, x)
 *          NOT(j = st--, i)
 *          AND(k = st--, i, a)
 *          AND(l = st--, j, b)
 *          ADD(t, k, l)
 *          st += 4
 * - posso costruire un bool(a > b) ?
 *   idea: farlo bit a bit
 *      if msb(a) == 1 && msb(b) == 0:
 *          ans = 1
 *          set(b, null)
 */

#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) {
    id shifted;
    append_move(t, a);
    int shift = 1;
    for (; shift < B; shift <<= 1) {
        append_left(shifted.i, t, shift);
        append_or(t, t, shifted.i);
        append_right(shifted.i, t, shift);
        append_or(t, t, shifted.i);
    }
    append_left(shifted.i, t, B / 2);
    append_or(t, t, shifted.i);
    append_right(shifted.i, t, B / 2);
    append_or(t, t, shifted.i);
}

// 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); // not always necessary
    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_store(t, 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, oa.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); // so far, only 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_store(ans.i, 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: 0 / 10
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 25
• Subtask 5: 0 / 13
• Subtask 6: 0 / 29