Submission #818712

#	Time	Username	Problem	Language	Result	Execution time	Memory
818712		PixelCat	Bit Shift Registers (IOI21_registers)	C++17	23 / 100	1 ms	656 KiB

registers

#include "registers.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

// #define DEBUG
#ifdef DEBUG
#define PRINT(x) append_print(x)
#else
#define PRINT(x)
#endif

/*

function signatures:
  void append_move(int t, int x)
  void append_store(int t, std::vector<bool> v)
  void append_and(int t, int x, int y)
  void append_or(int t, int x, int y)
  void append_xor(int t, int x, int y)
  void append_not(int t, int x)
  void append_left(int t, int x, int p)
  void append_right(int t, int x, int p)
  void append_add(int t, int x, int y)
  void append_print(int t)

registers:
  0   input/output
  1   a[i]
  2   a[j]
  3   all 1's iff (a[i] - a[j] <  0)  => a[i] <  a[j]
  4   all 1's iff (a[i] - a[j] >= 0)  => a[i] >= a[j]
  5   min(a[i], a[j]) = m[1] & m[3] + m[2] & m[4]
  6   max(a[i], a[j]) = m[1] & m[4] + m[2] & m[3]
  7   mask for a[i]
  8   mask for a[i] (inversed)
  9   mask for a[j]
  10  mask for a[j] (inversed)

  49  number literal 1

*/

void make_mask(int r, int k, int i) {
    vector<bool> m(2000, 0);
    For(j, i * k, i * k + k - 1) {
        m[j] = 1;
    }
    append_store(r, m);
    append_not(r + 1, r);
}

void construct_instructions(int s, int n, int k, int q) {
    vector<bool> one(2000, 0);
    one[0] = 1;
    append_store(49, one);

    For(i, 1, n - 1) {
        make_mask(7, k, i);
        For(j, 0, i - 1) {
            make_mask(9, k, j);

            append_and(1, 0, 7);
            append_right(1, 1, k * i);
            append_and(2, 0, 9);
            append_right(2, 2, k * j);

            append_not(3, 2);
            append_add(3, 3, 49);
            append_add(3, 1, 3);
            append_right(3, 3, 1000);
            append_not(4, 3);

            append_and(11, 1, 3);
            append_and(12, 2, 4);
            append_add(5, 11, 12);
            append_and(11, 1, 4);
            append_and(12, 2, 3);
            append_add(6, 11, 12);

            append_left(5, 5, j * k);
            append_left(6, 6, i * k);

            append_and(0, 0, 8);
            append_and(0, 0, 10);
            append_or(0, 0, 5);
            append_or(0, 0, 6);
        }
    }
}

/*

0 2 1 1000
0 0
0 1
1 0
1 1
-1

move 1 0
right 1 1 1
and 0 0 1
0
0
0
1


1 2 1 1000
0 0
0 1
1 0
1 1
-1

move 1 0
right 1 1 1
and 2 0 1
or 3 0 1
left 3 3 1
or 0 2 3
0 0
0 1
0 1
1 1


0 100 10 4000
-1

0 2 2 1000
00 00
00 01
00 10
00 11
01 00
01 01
01 10
01 11
10 00
10 01
10 10
10 11
11 00
11 01
11 10
11 11
-1

0 3 3 1000
010 100 111
101 111 100
000 000 011
-1

*/

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