제출 #820215

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
820215		LittleCube	Bit Shift Registers (IOI21_registers)	C++17	100 / 100	2 ms	628 KiB

registers

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

const int M = 100, B = 2000;

void keep_prefix(int x, int l)
{
	append_left(x, x, B - l);
	append_right(x, x, B - l);
}

void or_numbers(int n, int k, int t, int x)
{
	/*
		bit or n k-bit numbers stored at first k bits
		x: array
		10, 11: working space
		12: empty filter
		t: output
	*/
	append_move(10, x);
	while (n > 1)
	{
		int m = (n + 1) / 2;
		append_right(11, 10, m * k);
		append_or(10, 11, 10);
		n = m;
	}
	keep_prefix(10, k);
	append_move(t, 10);
}

void construct_instructions(int s, int n, int k, int q)
{
	if (s == 0)
	{
		if (k == 1 && n == 2)
		{
			append_right(1, 0, 1);
			append_and(0, 1, 0);
		}
		else if (k == 2 && n == 2)
		{
			// check 2
			// if a ^ b == 3 add (a cycle shifted & b > 0)
			append_right(1, 0, 2);
			append_and(2, 0, 1); // a & b
			// append_print(2);

			append_right(10, 1, 1);
			append_left(11, 1, 1);
			append_or(12, 10, 11);
			append_left(20, 12, B - 2);
			append_right(20, 20, B - 2); // b cycle shifted
			// append_print(20);

			append_and(20, 0, 20); // a cycle shifted & b
			// append_print(20);

			append_xor(25, 0, 1); // a ^ b, only 3 is okay so...
			append_left(25, 25, B - 2);
			append_right(25, 25, B - 2);
			// append_print(25);
			append_left(26, 25, 1);
			append_right(27, 25, 1);
			append_or(28, 26, 27); // a ^ b cycle shifted
			// append_print(28);

			append_and(25, 25, 28); // a ^ b == 3
			// append_print(25);

			append_and(20, 20, 25); // and with (a cycle shifted & b > 0)
			vector<bool> two(B, 0);
			two[0] = two[1] = 1;
			append_store(30, two);
			append_add(31, 30, 20); // third bit is the answer
			append_right(31, 31, 2);
			append_add(0, 31, 2);
		}
		else
		{
			vector<bool> stupid(B, 0), full(B, 1), one(B, 0), kless1(B, 0), everyk(B, 0);
			for (int i = 0; i < n * k; i++)
				stupid[i] = 1;
			one[0] = 1;
			for (int i = 0; i < n * k; i++)
				if (i % k != k - 1)
					kless1[i] = 1;
				else
					everyk[i] = 1;

			append_store(5, stupid);
			append_store(6, full);
			append_store(7, one);
			append_store(8, kless1);
			append_store(9, everyk);
			append_xor(0, 0, 5);
			for (int i = k - 1; i >= 0; i--)
			{
				vector<bool> filter(B, 0);
				for (int j = i; j < n * k; j += k)
					filter[j] = 1;
				append_store(1, filter);
				append_and(2, 0, 1);
				append_right(2, 2, i);
				// if none of them has the bit, 4 stores all 1 and becomes all zero when added 1,
				// thus append_not again and set the filter to all 1
				append_not(4, 2);
				append_add(4, 4, 7);
				append_right(4, 4, B - 1);
				append_add(4, 4, 6);
				// using 111...110 to duplicate (but not-ed) first k-1 bits
				append_add(3, 2, 8);
				append_not(3, 3);
				append_xor(2, 3, 9);
				append_or(2, 4, 2);
				append_and(0, 2, 0);
				append_print(0);
			}
			or_numbers(n, k, 0, 0);
			append_xor(0, 0, 5);
			keep_prefix(0, k);
		}
	}
	else
	{

		vector<bool> even(B, 0), odd(B, 0);

		for (int i = 0; i < (n - 1) * k; i++)
			if (i / k % 2 == 0)
				even[i] = 1;
			else
				odd[i] = 1;
		append_store(5, even);
		append_store(6, odd);
		auto bubble = [&](int mask)
		{
			append_print(0);
			append_right(10, 0, k);
			append_xor(15, 10, 0);
			append_print(15);
			append_and(15, 15, mask);
			append_move(20, 15);
			append_move(35, 99);
			for (int i = 1; i < k; i++)
			{
				append_right(30, 20, i);
				append_or(35, 30, 35);
			}
			append_not(30, 35);
			append_and(20, 30, 20);
			append_print(20);
			append_and(20, 20, mask);
			append_print(20);
			append_and(40, 20, 0);
			append_add(50, 40, mask);
			append_right(50, 50, k);
			append_and(50, 50, mask);
			append_add(50, 50, mask);
			append_not(50, 50);
			append_and(50, 50, mask);
			append_and(15, 50, 15);
			append_left(60, 15, k);
			append_or(15, 60, 15);
			append_print(15);
			append_xor(0, 0, 15);
		};
		for (int i = 0; i <= n; i++)
			if (i % 2 == 0)
				bubble(5);
			else
				bubble(6);
		// 11010101010101
		// 00100000101000
	}
}

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