Submission #437955

#	Time	Username	Problem	Language	Result	Execution time	Memory
437955		galca	Bit Shift Registers (IOI21_registers)	C++17	58 / 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 < 2000; i += 2*k) {
		for (int j = 0; j < k; j++) {
			if (i+j < 2000) mask1[i+j] = true;
		}
		for (int j = 0; j < k; j++) {
			if (i + j + k < 2000) mask1[i + k + j] = false;
		}
	}
	std::vector<bool> one(2000);
	for (int i = 0; i < 2000; i += 2 * k) {
		if (i < 2000) one[i] = true;
		for (int j = 1; j < 2 * k; j++) {
			if (i + j < 2000) one[i + j] = false;
		}
	}
	append_store(2, mask1);
	append_not(3, 2);
	append_store(4, one);

	std::vector<bool> invalid(2000);
	for (int i = 0; i < n * k; i++) {
		invalid[i] = false;
	}
	for (int i = n*k; i < 2000; i++) {
		invalid[i] = true;
	}

	append_store(5, invalid);
	append_or(0, 0, 5);

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

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

		append_print(1);

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

		append_xor(5, 1, 2);
		append_add(5, 5, 4); // reg5 holds -b

		append_print(5);

		append_add(6, 5, 0); // reg6 holds a - b

		append_print(6);

		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);

		append_print(8);
		append_print(9);

		// 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: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 25 / 25
• Subtask 5: 0 / 13
• Subtask 6: 0 / 29