Submission #565226

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

registers

#include "registers.h"

#include <bits/stdc++.h>
#include <cassert>

const int M = 100;
const int B = 4;

using namespace std;
using val_t = bitset<B>;

vector<int> free_st;

constexpr val_t zero() {
	val_t res;
	for (int i = 0; i < (int)res.size(); ++i) res[i] = 0;
	return res;
}

constexpr val_t all() {
	val_t res;
	for (int i = 0; i < (int)res.size(); ++i) res[i] = 1;
	return res;
}

int m_alloc() {
	assert(!free_st.empty());
	int res = free_st.back();
	free_st.pop_back();
	return res;
}

void m_free(int x) {
	free_st.push_back(x);
}

void append_store(int x, const bitset<B>& b) {
	vector<bool> v(B);
	for (int i = 0; i < B; ++i) v[i] = b[i];
	append_store(x, v);
}

void reverse(int x) {
	auto msk = zero();
	msk.flip(0);

	append_not(x, x);
	int y = m_alloc();
	append_store(y, msk);
	append_add(x, x, y);
	m_free(y);
}

void min2(int w, int K, int A, int S) {
	int tmp = m_alloc();
	for (int i = K; i--; ) {
		auto msk = zero();
		msk.flip(S+i);
		msk.flip(S+A+i);

		int a = m_alloc();
		append_store(a, msk);
		append_store(tmp, msk);
		append_and(a, w, a);
		append_xor(a, a, tmp);

		/* replace 1...1 => 0...0 */ {
			auto msk = all();
			msk.flip(S+A+i);
			int b = m_alloc(), c = m_alloc();

			append_store(tmp, msk);
			append_and(b, a, tmp); // b != (a & tmp);
			append_left(b, b, A); // b != (b << A);
			append_and(b, b, a); // b != (b & a);

			append_right(b, b, A); // b != (b >> A);
			append_or(c, c, b); // c != (c | b);
			append_xor(a, a, c); // a != (a ^ c);

			m_free(b);
			m_free(c);
		}

		append_right(a, a, i); // a != (a >> i);
		append_print(a);

		/* if LOW > HIGH */ {
			auto msk = zero();
			msk.flip(S);

			int x = m_alloc(), y = m_alloc();

			append_store(tmp, msk); // tmp != msk;
			append_and(x, a, tmp); // x != (a & tmp);
			append_left(y, x, A); // y != (x << A);

			reverse(x); // x = -x;
			append_add(y, x, y); // y != (x + y);
			append_left(y, y, A); // y != (y << A);
			append_not(y, y); // y != ~y;
			append_and(w, w, y); // w != (w & y);

			m_free(x);
			m_free(y);
		}

		/* if LOW < HIGH */ {
			int y = m_alloc(), c = m_alloc();

			append_right(a, a, A); // a != (a >> A);
			append_store(tmp, msk); // tmp != msk;
			append_and(a, a, tmp); // a != (a & tmp);
			
			append_left(y, a, A); // y != (a << A);
			reverse(a); // x = -x
			append_add(y, a, y); // y != (a + y);	

			append_not(y, y); // y != ~y;
			append_and(w, w, y);  // w != (w & y);
			append_not(y, y); // y != ~y;
			append_right(y, y, A); // y != (y << A);
			
			append_and(c, w, y); // c != (w & y);
			append_right(c, c, A); // c != (c >> A);
			append_or(w, w, c); // w != (w | c);

			m_free(y);
			m_free(c);
		}

		m_free(a);
	}

	m_free(tmp);
}

void construct_instructions(int S, int N, int K, int Q) {

	for (int i = M; i--; ) free_st.push_back(i);

	int w = m_alloc();

	if (N == 2) {
		min2(w, K, K, 0);
	}
}

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