Submission #442197

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

registers

#include "registers.h"
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

// #define int long long
// #define double long double
using pii = pair<int, int>;
template<typename T>
using Prior = std::priority_queue<T>;
template<typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;

#define X first
#define Y second
#define eb emplace_back
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)

namespace {

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

/**
 * all values are stored in arr[0]
 * void append_move (int t, int y)          # arr[t] =  arr[y]
 * void append_store(int t, vector<bool> v) # arr[t] =  v
 * void append_and  (int t, int x, int y)   # arr[t] =  arr[x] & arr[y]
 * void append_or   (int t, int x, int y)   # arr[t] =  arr[x] | arr[y]
 * void append_xor  (int t, int x, int y)   # arr[t] =  arr[x] ^ arr[y]
 * void append_not  (int t, int x)          # arr[t] = ~arr[x]
 * void append_left (int t, int x, int p)   # arr[t] =  arr[x] << p
 * void append_right(int t, int x, int p)   # arr[t] =  arr[x] >> p
 * void append_add  (int t, int x, int y)   # arr[t] = (arr[x] + arr[y]) % (1 << 2000)
 * void append_print(int t)                 # print(arr[t])
**/

const int M = 100;
const int B = 2000;

const int mask_k = 10;
const int mask_1 = 11;

vector<bool> bitmask_k, bitmask_1;

void init(int N, int k) {
    /// uses 2 operations ///
    bitmask_k.assign(B, false);
    fill(begin(bitmask_k), begin(bitmask_k) + k, true);
    bitmask_1.assign(B, false);
    fill(begin(bitmask_1), begin(bitmask_1) + 1, true);
    append_store(mask_k, bitmask_k);
    append_store(mask_1, bitmask_1);
}

void store_inputs(int N, int k) {
    /// uses 2N - 2 operations ///
    /// store values in the last k bits for all registers ///
    /// any place higher than k bits is initialized as 0 ///
    for (int i = N-1; i >= 1; --i) {
        append_and(i, 0, mask_k);
        append_right(0, 0, k);
    }
}

void find_minimum_value(int N, int k) {
    /// N = 2, k \le 2 ///
    
    store_inputs(N, k);
    for (int i = 0; i < N; ++i) append_print(i);
    
    if (k == 1) {
        append_and(0, 0, 1);
        return;
    }
    
    /// ans = (a1'a0' + b1b0 + a1'b1) ? a : b ///
    
    const int oa1 = 20;
    const int oa0 = 21;
    const int xa1 = 22;
    const int xa0 = 23;
    
    const int ob1 = 30;
    const int ob0 = 31;
    const int xb1 = 32;
    const int xb0 = 33;
    
    const int xa1xa0 = 90;
    const int ob1ob0 = 91;
    const int xa1ob1 = 92;
    const int above_or = 93;
    const int above_or_left_1 = 94;
    
    const int oval = 70;
    const int xval = 71;
    
    const int and_a_oval = 40;
    const int and_b_xval = 41;
    
    append_move(oa1, 0), append_right(oa1, oa1, 1), append_not(xa1, oa1), append_and(xa1, xa1, mask_1);
    append_and(oa0, 0, mask_1), append_not(xa0, oa0), append_and(xa0, xa0, mask_1);
    append_move(ob1, 1), append_right(ob1, ob1, 1);
    append_and(ob0, 1, mask_1);
    
    append_and(xa1xa0, xa1, xa0);
    append_and(ob1ob0, ob1, ob0);
    append_and(xa1ob1, xa1, ob1);
    append_or(above_or, xa1xa0, ob1ob0), append_or(above_or, above_or, xa1ob1);
    
    append_left(above_or_left_1, above_or, 1);
    append_or(oval, above_or, above_or_left_1);
    append_not(xval, oval), append_and(xval, xval, mask_k);
    
    append_and(and_a_oval, 0, oval);
    append_and(and_b_xval, 1, xval);
    append_or(0, and_a_oval, and_b_xval);
    
    append_print(mask_k), append_print(mask_1);
    append_print(oa1), append_print(oa0), append_print(xa1), append_print(xa0);
    append_print(ob1), append_print(ob0)/*, append_print(xb1), append_print(xb0)*/;
    append_print(xa1xa0), append_print(ob1ob0), append_print(xa1ob1);
    append_print(above_or), append_print(above_or_left_1);
    append_print(oval), append_print(xval);
    append_print(and_a_oval), append_print(and_b_xval);
}

void sort_register(int N, int k) {
    
}

} /// end of namespace

void construct_instructions(int S, int N, int k, int Q) {
    init(N, k);
    if (S == 0) find_minimum_value(N, k);
    if (S == 1) sort_register(N, k);
}

Compilation message (stderr)

registers.cpp: In function 'void {anonymous}::find_minimum_value(int, int)':
registers.cpp:88:15: warning: unused variable 'xb1' [-Wunused-variable]
   88 |     const int xb1 = 32;
      |               ^~~
registers.cpp:89:15: warning: unused variable 'xb0' [-Wunused-variable]
   89 |     const int xb0 = 33;
      |               ^~~

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