oj.uz

Submission #818712

# Submission time Handle Problem Language Result Execution time Memory
818712 2023-08-10T06:26:31 Z PixelCat Bit Shift Registers (IOI21_registers) C++17
23 / 100
 1 ms 656 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   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.0 / 10.0

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

Subtask #2
0.0 / 11.0

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

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 656 KB Wrong answer detected in grader
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 25.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 #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 428 KB Output is correct

Subtask #6
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 428 KB Output is correct
3 Incorrect 1 ms 592 KB Wrong answer detected in grader
4 Halted 0 ms 0 KB -