Submission #829558

#	Time	Username	Problem	Language	Result	Execution time	Memory
829558		_martynas	Bit Shift Registers (IOI21_registers)	C++17	21 / 100	1 ms	212 KiB

registers

#include "registers.h"

using namespace std;

const int M = 100;
const int B = 2000;
int T(int x) { return M-x; }

vector<bool> proper_size(vector<bool> arr) {
	vector<bool> proper(B, false);
	for(int i = 0; i < arr.size(); i++) proper[i] = arr[i];
	return proper;
}

/// @param s type of task
/// @param n number of integers in input
/// @param k number of bits in each input integer
/// @param q maximum number of instructions allowed
void construct_instructions(int s, int n, int k, int q) {
	if(s != 0) return;
	if(k == 1) {
		append_move(1, 0);
		append_right(1, 1, 1);
		append_and(0, 0, 1);
	}
	else if(k == 2) {
		append_move(1, 0);
		append_right(1, 1, 2);
		append_store(T(1), proper_size(vector<bool>{true, true}));
		append_and(0, 0, T(1));
		// r[0] is a[0], r[1] is a[1]
		append_xor(T(2), 0, 1);
		// r[T2] stores a[0] and a[1] xor
		// swap a[0] and a[1] by xoring a[0] with (a[0] xor a[1])
		// don't swap a[0] by xoring with 0
		// new problem: compare a[0] and a[1] to obtain a bit if a[0] > a[1]
		// b = (a[0][1] != a[1][1] && a[0][1] == 1) || (a[0][1] == a[1][1] && a[0][0] != a[1][0] && a[0][0] == 1)
		append_and(T(5), T(2), 0);
		append_right(T(5), T(5), 1);
		// r[T5] - (a[0][1] != a[1][1] && a[0][1] == 1)
		append_right(T(6), T(2), 1);
		append_not(T(6), T(6));
		// r[T6][0] - a[0][1] == a[1][1]
		append_and(T(7), T(2), 0);
		// r[T7] - a[0][0] != a[1][0] && a[1][0] == 1
		append_and(T(6), T(6), T(7));
		append_or(T(5), T(5), T(6));
		append_right(T(1), T(1), 1);
		append_and(T(5), T(5), T(1));
		append_left(T(8), T(5), 1);
		append_or(T(8), T(8), T(5));
		append_and(T(2), T(2), T(8));
		append_xor(0, 0, T(2));
	}
}

Compilation message (stderr)

registers.cpp: In function 'std::vector<bool> proper_size(std::vector<bool>)':
registers.cpp:11:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for(int i = 0; i < arr.size(); i++) proper[i] = arr[i];
      |                 ~~^~~~~~~~~~~~

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