Submission #1201168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201168		eliiasg	Bit Shift Registers (IOI21_registers)	C++20	100 / 100	1 ms	744 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 EVEN_OVERFLOW_FLAG = 96;
const int ODD_OVERFLOW_FLAG = 95;
const int INPUT = 0;
const int OFFSET_INPUT = 5;
const int OFFSET_INPUT_UP = 6;
const int A = 1;
const int B = 2;
const int ADD_RES = 3;
const int ADD_RES_1 = 4;

void initialize(int n, int k, int s)
{
	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(EVEN_OVERFLOW_FLAG, overflow_flag);
	append_store(REM_FLAG, rem_flag);
	if (s == 1)
	{
		append_left(ODD_OVERFLOW_FLAG, EVEN_OVERFLOW_FLAG, k);
		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_right(B, INPUT, align);
	append_and(B, B, EVEN_FLAG);
	append_and(INPUT, INPUT, EVEN_FLAG);
	// do a + !b
	append_not(ADD_RES, B);
	append_add(ADD_RES, ADD_RES, INPUT);
	// isolate overflow bit
	append_and(ADD_RES, ADD_RES, EVEN_OVERFLOW_FLAG);
	int mx = k + 1;
	int cur = 1;
	while (cur < mx)
	{
		int neww = min(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(INPUT, INPUT, ADD_RES);
	append_not(ADD_RES, ADD_RES);
	append_and(B, B, ADD_RES);
	append_or(INPUT, INPUT, B);
}

void do_swap(int k, bool invert)
{
	// overview:
	// Do a + !b
	// Overflow bit indicates larger num
	// Extrapolate(?) overflow to bitmask
	// Swap

	// align numbers
	int flag = invert ? ODD_FLAG : EVEN_FLAG;
	int other_flag = invert ? EVEN_FLAG : ODD_FLAG;
	int overflow = invert ? ODD_OVERFLOW_FLAG : EVEN_OVERFLOW_FLAG;
	append_right(OFFSET_INPUT, INPUT, k);
	append_left(OFFSET_INPUT_UP, INPUT, k);
	append_and(A, INPUT, flag);
	append_not(ADD_RES, OFFSET_INPUT);
	append_and(ADD_RES, ADD_RES, flag);
	// do a + !b
	append_add(ADD_RES, ADD_RES, A);
	// isolate overflow bit
	append_and(ADD_RES, ADD_RES, overflow);
	append_left(ADD_RES, ADD_RES, k - 1);
	int mx = k * 2;
	int cur = 1;
	while (cur < mx)
	{
		int neww = min(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);
	}
	// find up and down to keep
	append_and(OFFSET_INPUT_UP, OFFSET_INPUT_UP, other_flag);
	append_and(OFFSET_INPUT_UP, OFFSET_INPUT_UP, ADD_RES);
	append_and(OFFSET_INPUT, OFFSET_INPUT, flag);
	append_and(OFFSET_INPUT, OFFSET_INPUT, ADD_RES);
	// keep relavent input
	append_not(ADD_RES, ADD_RES);
	append_and(INPUT, INPUT, ADD_RES);
	// union
	append_or(INPUT, INPUT, OFFSET_INPUT_UP);
	append_or(INPUT, INPUT, OFFSET_INPUT);
}

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

void solve_s1(int n, int k)
{
	for (int i = 0; i < n / 2 + 25; i++)
	{
		do_swap(k, false);
		do_swap(k, true);
	}
}

void construct_instructions(int s, int n, int k, int q)
{
	initialize(n, k, s);
	if (s == 0)
		solve_s0(n, k);
	else
		solve_s1(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