Submission #437881

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

registers

#include "registers.h"

void construct_instructions(int s, int n, int k, int q) {
	append_print(0);
	
	std::vector<bool> mask1(2000);
	for (int i = 0; i < n*2*k; i += 2*k) {
		for (int j = 0; j < k; j++) {
			mask1[i+j] = true;
		}
		for (int j = 0; j < k; j++) {
			mask1[i + k + j] = false;
		}
	}
	std::vector<bool> one(2000);
	for (int i = 0; i < n * 2 * k; i += 2 * k) {
		mask1[i] = true;
		for (int j = 1; j < 2 * k; j++) {
			mask1[i + j] = false;
		}
	}
	append_store(2, mask1);
	append_not(3, 2);
	append_store(4, one);

	int msb = 0x1;
	int logn = 1;
	while (msb < n) {
		msb <<= 1;
		++logn;
	}

	for (int i = 0; i < logn; i++) {
		append_move(1, 0);
		append_right(1, 1, k*(1 << i));

		append_and(0, 0, 2); // reg0 holds a (even)
		append_and(1, 1, 3); // reg1 holds b (odd)

		append_xor(5, 1, 2);
		append_add(5, 5, 4); // reg5 holds -b
		append_add(6, 5, 0); // reg6 holds a - b

		append_move(7, 0);
		// if a > b, overflow bit is 1
		// if a < b, overflow bit is 0
		append_and(6, 6, 3); // reg6 holds the overflow of a-b
		append_add(6, 6, 3); // reg6 holds ffff if a is the min, 0 otherwise
		append_right(8, 6, k); // reg8 aligns the mask against the val
		append_not(9, 8);
		// move min to 0
		append_and(10, 7, 8);
		append_and(11, 1, 9);
		append_or(0, 10, 11);
		// move max to 1 - no need for min only
		//append_and(10, 7, 9);
		//append_and(11, 1, 8);
		//append_or(1, 10, 11);
	}
}

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