Submission #437084

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

registers

#include <assert.h>
#include "registers.h"

#define NUM_BITS 2000

static inline int ulong(int n) {
	int l = 0;
	while((1 << l) < n) l++;
	return l;
}

void calc_min(int n, int k) {
	//Fill rest of registers with 1s
	{
		std::vector<bool> r(NUM_BITS);
		for(int b = 0; b < NUM_BITS; b++) r[b] = (b >= n*k);
		append_store(1, r);
		append_or(0, 0, 1);
	}

	//Register plane algorithm
	for(int i = 0; i < ulong(n); i++) {
		//Split registers into two planes
		append_move(1, 0);
		append_right(1, 1, (1 << i) * k);

		//Calculate comparsion-add operands
		append_xor(2, 0, 1);
		append_and(3, 2, 0);
		append_and(4, 2, 1);
		append_not(4, 4);

		//Mask operands
		std::vector<bool> m(NUM_BITS);
		for(int b = 0; b < NUM_BITS; b++) m[b] = ((b % (1 << (i+1))) == 0);
		append_store(5, m);
		append_and(3, 3, 5);
		append_and(4, 4, 5);

		//Calculate comparison masks (0 if a is bigger)
		append_add(3, 3, 4);
		append_right(3, 3, k);

		append_store(4, std::vector<bool>(NUM_BITS, true));
		append_add(3, 3, 4);
		append_and(3, 3, 5);

		//Update operands
		append_and(0, 0, 3);
		append_not(3, 3);
		append_and(1, 1, 3);
		append_or(0, 0, 1);
	}
}

void sort_array(int n, int k) {
	assert(false);
}

void construct_instructions(int s, int n, int k, int q) {
	if(s == 0) calc_min(n, k);
	else if(s == 1) sort_array(n, k);
	else assert(false);
}

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