Submission #492711

#	Time	Username	Problem	Language	Result	Execution time	Memory
492711		altalk	Bit Shift Registers (IOI21_registers)	C++17	89 / 100	2 ms	460 KiB

registers

#include "registers.h"
#include <vector>
#include <iostream>
#define loop(a, b) for(int a = 0; a < b; a++)

constexpr int TASK_MIN = 0;
constexpr int TASK_SORT = 1;


constexpr int BIT_COUNT = 2000;

constexpr int REGISTER_1 = 99;
constexpr int REGISTER_2K = 98;
constexpr int REGISTER_C = 97;
constexpr int REGISTER_EXTRA = 96;

constexpr int REGISTER_IO = 0;
constexpr int REGISTER_A = 1;
constexpr int REGISTER_B = 2;


void sortPrepare(int s, int n, int k, int q) {
	// constants
	std::vector<bool> gen_1(BIT_COUNT);
	loop(a, n/2 + 1) gen_1[(a+1) * (2*k) - 1] = 1;
	append_store(REGISTER_1, gen_1);

	std::vector<bool> gen_2k(BIT_COUNT);
	loop(a, n/2 + 1) loop(b, k) gen_2k[(a+1) * (2*k) - (b+1)] = 1;
	append_store(REGISTER_2K, gen_2k);

	std::vector<bool> gen_c(BIT_COUNT);
	loop(a, n/2 + 1) gen_c[(a+1) * (2*k) - k] = 1;
	append_store(REGISTER_C, gen_c);

	std::vector<bool> gen_extra(BIT_COUNT);
	loop(a, 2*k) gen_extra[n * k + a] = 1;
	append_store(REGISTER_EXTRA, gen_extra);

	// extra char
	append_or(REGISTER_IO, REGISTER_IO, REGISTER_EXTRA);

	// shift the A
	append_left(REGISTER_A, REGISTER_IO, k);

	// mask both A and B
	append_and(REGISTER_B, REGISTER_IO, REGISTER_2K);
	append_and(REGISTER_A, REGISTER_A, REGISTER_2K);

	
}

void sortSmaller(int s, int n, int k, int q, int REGISTER_SMALL, int REGISTER_BIG) {
	constexpr int REGISTER_NB = 3;
	append_not(REGISTER_NB, REGISTER_B);
	append_and(REGISTER_NB, REGISTER_NB, REGISTER_2K);

	constexpr int REGISTER_SUM = 4;
	append_add(REGISTER_SUM, REGISTER_A, REGISTER_NB);

	constexpr int REGISTER_SUM_CARRY = 5;
	append_right(REGISTER_SUM_CARRY, REGISTER_SUM, k);
	append_and(REGISTER_SUM_CARRY, REGISTER_SUM_CARRY, REGISTER_C);

	constexpr int REGISTER_MASK2 = 7;
	append_add(REGISTER_MASK2, REGISTER_SUM_CARRY, REGISTER_2K);
	append_and(REGISTER_MASK2, REGISTER_MASK2, REGISTER_2K);

	constexpr int REGISTER_MASK1 = 6;
	append_not(REGISTER_MASK1, REGISTER_MASK2);

	constexpr int REGISTER_PARTA1 = 8;
	constexpr int REGISTER_PARTA2 = 9;
	constexpr int REGISTER_PARTB2 = 10;
	constexpr int REGISTER_PARTB1 = 11;
	append_and(REGISTER_PARTA1, REGISTER_A, REGISTER_MASK1);
	append_and(REGISTER_PARTA2, REGISTER_A, REGISTER_MASK2);
	append_and(REGISTER_PARTB2, REGISTER_B, REGISTER_MASK2);
	append_and(REGISTER_PARTB1, REGISTER_B, REGISTER_MASK1);

	append_or(REGISTER_BIG, REGISTER_PARTA1, REGISTER_PARTB2);
	append_or(REGISTER_SMALL, REGISTER_PARTA2, REGISTER_PARTB1);
}

void sort_shake(int s, int n, int k, int q) {
	sortSmaller(s, n, k, q, REGISTER_A, REGISTER_B);
	append_left(REGISTER_B, REGISTER_B, 2*k);
	sortSmaller(s, n, k, q, REGISTER_B, REGISTER_A);
	append_right(REGISTER_B, REGISTER_B, 2*k);
}

void construct_instructions(int s, int n, int k, int q) {
	
	if (s == TASK_SORT) {
		sortPrepare(s, n, k, q);
		// append_print(REGISTER_IO);
		// append_print(REGISTER_A);
		// append_print(REGISTER_B);
		loop(a, n / 2){
			sort_shake(s, n, k, q);
			// append_print(REGISTER_A);
			// append_print(REGISTER_B);
		}
		if (n % 2 == 1) sortSmaller(s, n, k, q, REGISTER_A, REGISTER_B);
		append_right(REGISTER_A, REGISTER_A, k);
		append_or(REGISTER_IO, REGISTER_A, REGISTER_B);
	}
	else if (s == TASK_MIN) {
		sortPrepare(s, n, k, q);
		// append_print(REGISTER_IO);
		// append_print(REGISTER_A);
		// append_print(REGISTER_B);
		while (n > 1) {
			sortSmaller(s, n, k, q, REGISTER_A, REGISTER_B);
			n = (n + 1) / 2;
			append_right(REGISTER_B, REGISTER_A, (2*k) * (n/2) );
			// append_print(REGISTER_A);
			// append_print(REGISTER_B);
		}
		append_right(REGISTER_A, REGISTER_A, k);
		append_or(REGISTER_IO, REGISTER_A, REGISTER_B);
	}
}

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