oj.uz

Submission #821372

# Submission time Handle Problem Language Result Execution time Memory
821372 2023-08-11T09:37:31 Z PixelCat Bit Shift Registers (IOI21_registers) C++17
64 / 100
 4 ms 1044 KB 
#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  input/output (shifted right for k bits)
  2  mask for useful segments (every other numbers)
  3  mask for first bits of every useful segments
  4  (m[0] ^ m[1]) & m[2] (XORs of adjacent numbers)
  5  hi-bit of XORs of adjacent numbers
  6  m[0] & m[5] (should this pair be swapped?)
  7  'expanded' m[6]
  8  m[7] & m[4] (swapping key for every pair of numbers)

*/

// cost = 8
void expand_right(int r, int k) {
    int j = 1;
    while(j < k) {
        int j2 = min(j * 2, k) - j;
        append_right(49, r, j2);
        append_or(r, r, 49);
        j += j2;
    }
}

// cost = 2
// s = 0 or 1
void make_masks(int n, int k, int s) {
    vector<bool> m2(2000, 0);
    vector<bool> m3(2000, 0);
    for(int i = s; i < n - 1; i += 2) {
        m3[i * k] = 1;
        For(j, 0, k - 1) m2[i * k + j] = 1;
    }
    append_store(2, m2);
    append_store(3, m3);
}

void construct_instructions(int s, int n, int k, int q) {
    int parity = 1;
    For(_, 0, n) {

        parity = 1 - parity;
        make_masks(n, k, parity);
        append_right(1, 0, k);
        append_xor(4, 0, 1);
        append_and(4, 4, 2);  // 5

        append_move(5, 4);
        expand_right(5, k);
        append_and(5, 5, 2);
        append_add(5, 5, 3);
        append_right(5, 5, 1);  // 12

        if(_ == 0) {
            PRINT(0);
            PRINT(1);
            PRINT(2);
            PRINT(3);
            PRINT(4);
            PRINT(5);
        }

        append_and(6, 0, 5);
        append_left(7, 6, k - 1);
        expand_right(7, k * 2 - 1);  // 12

        append_and(8, 7, 4);
        if(_ == 0) {
            PRINT(6);
            PRINT(7);
            PRINT(8);
        }
        append_xor(0, 0, 8);
        append_left(8, 8, k);
        append_xor(0, 0, 8);  // 4
    }
}

/*

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

*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #2
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Wrong answer detected in grader
2 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 1028 KB Output is correct
3 Correct 4 ms 996 KB Output is correct
4 Correct 3 ms 1044 KB Output is correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 300 KB Wrong answer detected in grader
2 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #6
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 4 ms 1008 KB Output is correct
4 Correct 3 ms 1008 KB Output is correct
5 Correct 3 ms 788 KB Output is correct
6 Correct 3 ms 788 KB Output is correct
7 Correct 2 ms 788 KB Output is correct