Submission #636712

#	Time	Username	Problem	Language	Result	Execution time	Memory
636712		imeimi2000	Bit Shift Registers (IOI21_registers)	C++17	100 / 100	2 ms	596 KiB

registers

#include "registers.h"

using namespace std;

const int B = 2000;

void solve1(int n, int k, bool first = true) {
	if (n == 1) return;
	const int MASK = 97;
	const int MSB = 98;
	const int ONE = 99;
	vector<bool> mask, msb, one(B, false), fill;
	one[0] = true;
	mask.reserve(B);
	msb.reserve(B);
	fill.reserve(B);
	for (int i = 0; i < B; ++i) {
		mask.push_back(i / k % 2 == 0);
		msb.push_back(!mask[i] && i % k == 0);
		fill.push_back(n * k <= i);
	}
	if (first) {
		if (n > 2) {
			append_store(99, fill);
			append_add(0, 0, 99);
		}
		append_store(ONE, one);
	}
	append_store(MASK, mask);
	append_store(MSB, msb);

	append_or(3, 0, MSB);

	append_right(2, 0, k);
	append_and(2, 2, MASK);
	append_not(4, 2);
	append_add(4, 4, ONE);

	append_add(3, 3, 4);
	append_and(3, 3, MSB);
	append_right(4, 3, k);
	append_not(4, 4);
	append_add(4, 4, ONE);
	append_add(3, 3, 4);
	append_not(4, 3);
	append_and(4, 4, MASK);

	append_and(1, 0, 4);
	append_and(2, 2, 3);
	append_add(0, 1, 2);
	append_print(0);
	solve1((n + 1) / 2, k * 2, false);
}

void solve2(int n, int k) {
	const int FILL = 96;
	const int MASK = 97;
	const int MSB = 98;
	const int ONE = 99;
	vector<bool> mask, msb, one(B, false), fill;
	one[0] = true;
	mask.reserve(B);
	msb.reserve(B);
	fill.reserve(B);
	for (int i = 0; i < B; ++i) {
		mask.push_back(i / k % 2 == 0);
		msb.push_back(!mask[i] && i % k == 0);
		fill.push_back(n * k <= i);
	}
	append_store(FILL, fill);
	append_add(0, 0, FILL);
	append_store(ONE, one);
	append_store(MASK, mask);
	append_store(MSB, msb);
	for (int i = 0; i < n + 5; ++i) {
		if (i & 1) {
			append_left(0, 0, k);
		}
		append_or(1, 0, MSB);
		append_right(2, 0, k);
		append_and(2, 2, MASK);
		append_not(3, 2);
		append_add(3, 3, ONE);
		append_add(3, 1, 3);
		append_and(3, 3, MSB);
		append_right(4, 3, k);
		append_not(4, 4);
		append_add(4, 4, ONE);
		append_add(3, 3, 4);
		append_not(4, 3);
		append_and(1, 0, MASK);
		append_and(0, 1, 4); // first min
		append_and(6, 1, 3); // first max
		append_left(6, 6, k);
		append_add(0, 0, 6);
		append_and(7, 2, 3); // second min
		append_add(0, 0, 7);
		append_and(8, 2, 4); // second max
		append_left(8, 8, k);
		append_add(0, 0, 8);
		if (i & 1) {
			append_right(0, 0, k);
			append_or(0, 0, FILL);
		}
	}
}

void construct_instructions(int s, int n, int k, int q) {
	if (s == 0) solve1(n, k);
	else solve2(n, k);
}

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