Submission #1068745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068745		c2zi6	Bit Shift Registers (IOI21_registers)	C++17	13 / 100	1 ms	348 KiB

registers

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "registers.h"

const int B = 2000;
/*const int B = 60;*/
const int M = 100;
int k;

const int INT_ONE = 90;
const int BOOL_TRUE = 91;
const int K_ONES = 92;
/* REGISTERS [90, 98] ARE RESERVED FOR CONSTANTS */

void add_constants() {
    vector<bool> ret;
    ret = vector<bool>(B, 0);
    ret[0] = 1;
    append_store(INT_ONE, ret);
    ret = vector<bool>(B, 1);
    append_store(BOOL_TRUE, ret);
    ret = vector<bool>(B, 0);
    rep(i, k) ret[i] = 1;
    append_store(K_ONES, ret);
}

/* 2 operations */
void append_neg(int res, int reg1) {
    append_not(res, reg1);
    append_add(res, res, INT_ONE);
}

/* 3 operations */
void append_sub(int res, int reg1, int reg2) {
    append_neg(res, reg2);
    append_add(res, res, reg1);
}

/* 2 operations */
void append_sign(int res, int reg1) {
    /* true if reg1 >= 0 */
    append_right(res, reg1, B-1);
    append_add(res, res, BOOL_TRUE);
}

/* 5 operations */
void append_ge(int res, int reg1, int reg2) {
    append_sub(res, reg1, reg2);
    append_sign(res, res);
}

/* 5 operations */
void append_le(int res, int reg1, int reg2) {
    append_sub(res, reg2, reg1);
    append_sign(res, res);
}

/* 4 operations */
void append_mux(int res, int statement, int reg1, int reg2) {
    append_not(88, statement);
    append_and(89, statement, reg1);
    append_and(res, 88, reg2);
    append_or(res, res, 89); 
}

/* 9 operations */
void append_min(int res, int reg1, int reg2) {
    append_le(87, reg1, reg2);
    append_mux(res, 87, reg1, reg2);
}

/* 9 operations */
void append_max(int res, int reg1, int reg2) {
    append_le(86, reg2, reg1);
    append_mux(res, 86, reg1, reg2);
}

/* 20 operations */
void append_sort(int reg1, int reg2) {
    append_max(85, reg1, reg2);
    append_min(84, reg1, reg2);
    append_move(reg1, 84);
    append_move(reg2, 85);
}

/* 4 operations */
void append_zero(int res, int reg1) {
    append_neg(res, reg1);
    append_sign(res, res);
}

void construct_instructions(int s, int n, int k_arg, int q) {k = k_arg;
    add_constants();
    if (s == 0) {
        vector<bool> ptr(B, 0);
        rep(i, n) ptr[k*i + k-1] = 1;
        vector<bool> ansptr(B, 0);
        ansptr[k-1] = 1;

        append_store(1, ptr);
        append_store(4, ansptr);

        rep(i, k) {
            append_and(2, 0, 1);
            append_xor(2, 1, 2);

            append_zero(5, 2);
            append_not(3, 5);

            append_and(6, 5, 4);
            append_or(7, 7, 6);

            if (i) {
                append_right(4, 4, 1);
                append_mux(1, 3, 2, 1);
                append_right(1, 1, 1);
            }
        }


        append_move(0, 7);
    } else {
        replr(i, 1, n) {
            append_and(i, 0, K_ONES);
            append_right(0, 0, k);
        }
        reprl(l, n-1, 1) {
            replr(i, 1, l) {
                append_sort(i, i+1);
            }
        }
        reprl(i, n, 1) {
            append_left(0, 0, k);
            append_or(0, 0, i);
        }
    }
}

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