Submission #996809

#	Time	Username	Problem	Language	Result	Execution time	Memory
996809		MinaRagy06	Bit Shift Registers (IOI21_registers)	C++17	100 / 100	6 ms	1876 KiB

registers

#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;
#include "registers.h"
#ifdef MINA
#include "grader.cpp"
#endif

void construct_instructions(int s, int n, int k, int q) {
	int m = 100, b = 2000;
	int newn = 1;
	while (newn < n) {
		newn *= 2;
	}
	if (newn != n) {
		vector<bool> extra(b, 0);
		for (int i = n * k; i < newn * k; i++) {
			extra[i] = 1;
		}
		append_store(m - 1, extra);
		append_or(0, 0, m - 1);
		n = newn;
	}
	vector<int> pos(b);
	for (int i = 0; i < b; i++) {
		if (i / k < n) {
			pos[i] = i / k;
		} else {
			pos[i] = -1;
		}
	}
	if (s == 0) {
		int gap = k;
		bool stored_sign = 0;
		while (n > 1) {
			vector<bool> msk[2];
			msk[0].assign(b, 0);
			msk[1].assign(b, 0);
			for (int i = 0; i < b; i++) {
				if (pos[i] == -1) continue;
				msk[pos[i] & 1][i] = 1;
			}
			append_store(m - 1, msk[0]);
			append_and(1, 0, m - 1);
			append_store(m - 1, msk[1]);
			append_and(2, 0, m - 1);
			append_right(2, 2, gap);
			if (k != 1) {
				for (int i = 0; i < b; i++) {
					if (pos[i] == -1) continue;
					if ((pos[i] & 1) == 0) {
						pos[i] /= 2;
					} else {
						pos[i] = -1;
					}
				}
				vector<bool> ones(b);
				for (int i = 0; i < b; i++) {
					if (pos[i] != -1) {
						ones[i] = 1;
					}
				}
				append_store(m - 1, ones);
				append_add(3, 1, m - 1);
				append_xor(3, 3, m - 1);
				append_add(4, 2, 3);
				if (!stored_sign) {
					vector<bool> sign(b);
					for (int i = 1; i < b; i++) {
						if (pos[i] == -1 && pos[i - 1] != -1) {
							sign[i] = 1;
						}
					}
					append_store(m - 2, sign);
					stored_sign = 1;
				}
				append_and(4, 4, m - 2);
				int sz = 1;
				while (sz <= k) {
					int nxtsz = min(2 * sz, k + 1);
					append_right(m - 1, 4, nxtsz - sz);
					append_or(4, 4, m - 1);
					sz = nxtsz;
				}
				append_xor(5, 1, 2);
				append_and(5, 5, 4);
				append_xor(0, 1, 5);
			} else {
				append_and(0, 1, 2);
			}
			n /= 2;
			gap *= 2;
		}
	} else {
		for (int i = 0; i < b; i++) {
			if (pos[i] == -1) continue;
			if (pos[i] & 1) {
				pos[i] = -1;
			} else {
				pos[i] /= 2;
			}
		}
		for (int itr = 0; itr < n; itr++) {
			if ((itr & 1)) {
				vector<bool> msk(b, 0);
				for (int i = 0; i < k; i++) {
					msk[i] = 1;
				}
				for (int i = (n - 1) * k; i < n * k; i++) {
					msk[i] = 1;
				}
				append_store(m - 1, msk);
				append_and(m - 3, 0, m - 1);
				append_not(m - 1, m - 1);
				append_and(0, 0, m - 1);
				append_right(0, 0, k);
			}
			vector<bool> msk[2];
			msk[0].assign(b, 0);
			msk[1].assign(b, 0);
			for (int i = 0; i < b; i++) {
				if (i / k == n) {
					break;
				}
				msk[(i / k) & 1][i] = 1;
			}
			append_store(m - 1, msk[0]);
			append_and(1, 0, m - 1);
			append_store(m - 1, msk[1]);
			append_and(2, 0, m - 1);
			append_right(2, 2, k);
			append_print(1);
			append_print(2);
			if (k != 1) {
				vector<bool> ones(b);
				for (int i = 0; i < b; i++) {
					if (pos[i] != -1) {
						ones[i] = 1;
					}
				}
				append_store(m - 1, ones);
				append_add(3, 1, m - 1);
				append_xor(3, 3, m - 1);
				append_add(4, 2, 3);
				append_print(4);
				vector<bool> sign(b);
				for (int i = 1; i < b; i++) {
					if (pos[i] == -1 && pos[i - 1] != -1) {
						sign[i] = 1;
					}
				}
				append_store(m - 2, sign);
				append_and(4, 4, m - 2);
				int sz = 1;
				while (sz <= k) {
					int nxtsz = min(2 * sz, k + 1);
					append_right(m - 1, 4, nxtsz - sz);
					append_or(4, 4, m - 1);
					sz = nxtsz;
				}
				append_print(4);
				append_xor(5, 1, 2);
				append_and(6, 5, 4);
				append_xor(0, 1, 6);
				append_xor(5, 0, 5);
				append_left(5, 5, k);
				append_or(0, 0, 5);
			} else {
				append_and(0, 1, 2);
				append_xor(5, 1, 2);
				append_xor(5, 0, 5);
				append_left(5, 5, k);
				append_or(0, 0, 5);
			}
			if ((itr & 1)) {
				append_left(0, 0, k);
				append_or(0, 0, m - 3);
			}
			append_print(0);
		}
	}
}

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