Submission #507937

#	Time	Username	Problem	Language	Result	Execution time	Memory
507937		ITO	Bit Shift Registers (IOI21_registers)	C++17	100 / 100	2 ms	588 KiB

registers

#include "registers.h"
#include <bits/stdc++.h>
using namespace std;
vector<bool> fillend(2000), nummask(2000), add1(2000);
void construct_instructions(int s, int n, int k, int q) {
	for (int i = n * k; i < 2000; i++) {
		fillend[i] = 1;
	}
	for (int i = 0; i < 2000; i += 2 * k) {
		for (int j = i; j < i + k && j < 2000; j++) {
			nummask[j] = 1;
		}
		add1[i] = 1;
	}
	if (s == 0) {
		append_store(1, fillend);
		append_store(3, nummask);
		append_store(4, add1);
		append_or(0, 0, 1); // fill end with max
		append_right(10, 0, k); // position numbers
		append_and(0, 0, 3);
		int i = (n + 1) / 2;
		while(1) {
			append_not(11, 10);
			append_and(11, 11, 3);
			append_add(11, 11, 4);
			append_add(11, 0, 11); // 0 smaller when no overflow
			append_right(11, 11, k); // focus on overflow
			append_and(11, 11, 3); // clear garbage
			int j = 1;
			while (j < k) {
				append_left(12, 11, min(j, k - j));
				append_or(11, 11, 12);
				j *= 2;
			} // 10 smaller mask
			append_xor(12, 11, 3); // 0 smaller mask
			append_and(10, 10, 11);
			append_and(0, 0, 12);
			append_or(0, 0, 10);
			if (i == 1) {
				break;
			}
			i = (i + 1) / 2;
			append_right(10, 0, i * 2 * k);
		}
	} else {
		append_store(1, fillend);
		append_store(3, nummask);
		append_store(4, add1);
		append_or(0, 0, 1); // fill end with max
		append_right(10, 0, k); // position numbers
		append_and(0, 0, 3);
		for (int i = n / 2; i < n; i++) {
			append_not(11, 10);
			append_and(11, 11, 3);
			append_add(11, 11, 4);
			append_add(11, 0, 11); // 0 smaller when no overflow
			append_right(11, 11, k); // focus on overflow
			append_and(11, 11, 3); // clear garbage
			int j = 1;
			while (j < k) {
				append_left(12, 11, min(j, k - j));
				append_or(11, 11, 12);
				j *= 2;
			} // 10 smaller mask
			append_xor(12, 11, 3); // 0 smaller mask
			append_and(20, 0, 12);
			append_and(21, 0, 11);
			append_and(30, 10, 11);
			append_and(31, 10, 12);
			append_or(0, 20, 30);
			append_or(21, 21, 31);
			append_left(10, 21, k * 2);
			append_not(11, 10);
			append_and(11, 11, 3);
			append_add(11, 11, 4);
			append_add(11, 0, 11); // 0 smaller when no overflow
			append_right(11, 11, k); // focus on overflow
			append_and(11, 11, 3); // clear garbage
			j = 1;
			while (j < k) {
				append_left(12, 11, min(j, k - j));
				append_or(11, 11, 12);
				j *= 2;
			} // 10 smaller mask
			append_xor(12, 11, 3); // 0 smaller mask
			append_and(20, 0, 12);
			append_and(21, 0, 11);
			append_and(30, 10, 11);
			append_and(31, 10, 12);
			append_or(0, 21, 31);
			append_or(21, 20, 30);
			if (i == n - 1) {
				append_right(10, 21, k);
				append_or(0, 0, 10);
			} else {
				append_right(10, 21, k * 2);
			}
		}
	}
}

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