Submission #1200664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200664		eliiasg	Bit Shift Registers (IOI21_registers)	C++20	0 / 100	0 ms	328 KiB

registers

#include "registers.h"
#include "bits/stdc++.h"
using namespace std;

// used for storing 1's at the end of input, to not have 0's that kill min
const int REM_FLAG = 99;
const int EVEN_FLAG = 98;
const int ODD_FLAG = 97;
const int OVERFLOW_FLAG = 96;
const int INPUT = 0;
const int A = INPUT;
const int B = 1;
const int ADD_RES = 2;
const int ADD_RES_1 = 3;

void initialize(int n, int k)
{
	vector<bool> rem_flag(2000);
	vector<bool> even_flag(2000);
	vector<bool> overflow_flag(2000);
	for (int i = 0; i < 2000; i++)
	{
		rem_flag[i] = i >= n * k;
		even_flag[i] = (i / k) % 2 == 0;
		overflow_flag[i] = i % (k * 2) == k;
	}
	append_store(EVEN_FLAG, even_flag);
	append_store(OVERFLOW_FLAG, overflow_flag);
	append_store(REM_FLAG, rem_flag);
	append_not(ODD_FLAG, EVEN_FLAG);
	append_or(INPUT, INPUT, REM_FLAG);
}

void do_min(int k, int align)
{
	// overview:
	// Do a + !b
	// Overflow bit indicates larger num
	// Extrapolate(?) overflow to bitmask
	// Do (a & mask) | (b & !mask)

	// align numbers
	append_move(B, A);
	append_right(B, B, align);
	append_and(B, B, EVEN_FLAG);
	append_and(A, A, EVEN_FLAG);
	// do a + !b
	append_not(ADD_RES, B);
	append_add(ADD_RES, ADD_RES, B);
	// isolate overflow bit
	append_and(ADD_RES, ADD_RES, OVERFLOW_FLAG);
	int mx = k + 1;
	int cur = 1;
	while (cur < mx)
	{
		int neww = max(cur * 2, mx);
		int diff = neww - cur;
		cur = neww;
		append_right(ADD_RES_1, ADD_RES, diff);
		append_or(ADD_RES, ADD_RES, ADD_RES_1);
	}

	// Do (a & mask) | (b & !mask)
	append_and(B, B, ADD_RES);
	append_not(ADD_RES, ADD_RES);
	append_add(A, A, ADD_RES);
	append_or(A, A, B);
}

void construct_instructions(int s, int n, int k, int q)
{
	initialize(n, k);
	int sk = 1;
	int lk = 1;
	while (sk < k)
	{
		sk *= 2;
		++lk;
	}
	int align = k;
	for (int i = 0; i < lk; i++)
	{
		do_min(k, align);
		align *= 2;
	}
}

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