Submission #624117

#	Time	Username	Problem	Language	Result	Execution time	Memory
624117		Temmie	Bit Shift Registers (IOI21_registers)	C++17	100 / 100	1 ms	596 KiB

registers

/*
 * 
 * get a 1 bit on b10 if x <= y and 0 bit otherwise (in reg2)
 * where x is number on bit 0..9 in reg0 and y is number on bit 0..9 in reg1
 * z is 11 bit number in reg2 on bit 0..10
 * make z -> -y - 1 by doing y ^ 0b11111111111 (11 ones)
 * make z -> z + x
 * if bit 11 is on in reg2: x <= y since number is still negative
 * else: x > y
 * 
 * preset:
 * 1 mask 00..0011..1100..0011..11...
 * 2 mask 0x10 1 0x9 0x10 1 ...
 * 3 mask to save value to regS in offset 0
 * 4 mask to save value(s) to regS in offset 1
 * 
 * 1  store potential last value in reg0 into regS with and operator with preset 1bits-mask (if n is odd)
 * 1  take all odd numbers from reg0 and copy them to reg1:
 * 2  use mask 00..0011..1100..0011..11... to get reg1 with only odd indices
 * 3  shift to the left by 10 to align with reg0
 * 5  perform above steps to get x ?<= y bits for each number in parallel
 * 6  filer out all stray bits by using mask with 0x10 1 0x9 0x10 1 ...
 * 7  then shift to the left by 1 and or that on
 * 8  then shift to the left by 2 and or that on
 * 9  then shift to the left by 4 and or that on
 * 10 then shift to the left by 2 and or that on to get 11 ones if b10 was 1 and zeroes otherwise
 * 11 then and the resulting mask with reg1 to get potential values where y >= x
 * 13 then perform not operator on the mask and perform and operator on reg0 to get values where x > y
 * 15 then shift to the right by 10 and or the result to regT to insert the elements
 * 17 then set regU to reg0 xor reg1 xor reg2 to get a register with the values with the lesser values
 * 18 insert regU into regT with or and move result to reg0
 * 19 or in the stored value in regS
 * 
 * repeat above step but starting with index 1
 * store value 0 (always) and potential last value (if n is even) like step 1 in above sequence
 * 
 * repeat n times where offset (0 or 1) is alternated between (about half each)
 * 
*/

#include "registers.h"
#include <bits/stdc++.h>

int s, n, k, q;
int alter = 99;
int bkp1 = 98;
int regS0 = 97;
int regS1 = 96;
int nregS0 = 95;
int nregS1 = 94;
int regStore = 93;
int kp1ones = 92;
int nalter = 91;

// 7 queries
void prepare_masks() {
	std::vector <bool> mask(2000, 0);
	for (int i = 1; i < n; i += 2) {
		int start = i * k;
		for (int j = 0; j < k; j++) {
			mask[start + j] = 1;
		}
	}
	append_store(alter, mask);
	mask.assign(2000, 0);
	for (int i = 0; i < n; i += 2) {
		int start = i * k + k;
		mask[start] = 1;
	}
	append_store(bkp1, mask);
	mask.assign(2000, 0);
	if (n & 1) {
		int start = (n - 1) * k;
		for (int j = 0; j < k; j++) {
			mask[start + j] = 1;
		}
	}
	append_store(regS0, mask);
	mask.assign(2000, 0);
	for (int j = 0; j < k; j++) {
		mask[j] = 1;
	}
	if (~n & 1) {
		int start = (n - 1) * k;
		for (int j = 0; j < k; j++) {
			mask[start + j] = 1;
		}
	}
	append_store(regS1, mask);
	append_not(nregS0, regS0);
	append_not(nregS1, regS1);
	mask.assign(2000, 0);
	for (int i = 0; i < n; i += 2) {
		int start = i * k;
		for (int j = 0; j < k + 1; j++) {
			mask[start + j] = 1;
		}
	}
	append_store(kp1ones, mask);
	append_not(nalter, alter);
}

// 3 queries
void compare_even_pos() {
	append_xor(2, kp1ones, 1);
	append_add(2, 2, 0);
	append_and(2, 2, bkp1);
}

// 22 queries worst case
void go0() {
	append_and(regStore, 0, regS0);
	append_and(0, 0, nregS0);
	append_and(1, 0, alter);
	append_right(1, 1, k);
	append_and(0, nalter, 0);
	compare_even_pos();
	append_right(2, 2, 1);
	int left = k - 1;
	int sofar = 1;
	while (left) {
		if (sofar <= left) {
			append_right(3, 2, sofar);
			append_or(2, 2, 3);
			left -= sofar;
			sofar <<= 1;
		} else {
			append_right(3, 2, left);
			append_or(2, 2, 3);
			break;
		}
	}
	append_and(3, 2, 1);
	append_not(2, 2);
	append_and(4, 2, 0);
	append_or(3, 3, 4);
	// now register 3 has value of greater number between the two compared values
	append_xor(4, 3, 0);
	append_xor(4, 4, 1);
	// now register 4 has value of lesser number betweren the two compared values
	append_left(3, 3, k);
	append_or(0, 4, 3);
	// now register 0 has result of bubbel sort step
	append_or(0, 0, regStore);
	// now register 0 has stray value too
}

// 22 queries worst case
void go1() {
	append_and(regStore, 0, regS1);
	append_and(0, 0, nregS1);
	append_and(1, 0, alter);
	append_left(1, 1, k);
	append_and(0, nalter, 0);
	compare_even_pos();
	append_right(2, 2, 1);
	int left = k - 1;
	int sofar = 1;
	while (left) {
		if (sofar <= left) {
			append_right(3, 2, sofar);
			append_or(2, 2, 3);
			left -= sofar;
			sofar <<= 1;
		} else {
			append_right(3, 2, left);
			append_or(2, 2, 3);
			break;
		}
	}
	append_and(3, 2, 1);
	append_not(2, 2);
	append_and(4, 2, 0);
	append_or(3, 3, 4);
	// now register 3 has value of greater number between the two compared values
	append_xor(4, 3, 0);
	append_xor(4, 4, 1);
	// now register 4 has value of lesser number betweren the two compared values
	append_right(4, 4, k);
	append_or(0, 4, 3);
	// now register 0 has result of bubbel sort step
	append_or(0, 0, regStore);
	// now register 0 has stray value too
}

//0 1 2 3 4 5 6 7
//0   2   4   6
//0       4
//0

//0 1 2 3 4 5 6 7 8 9
//0   2   4   6   8
//0       4       8

void solve_s0() {
	
	{
		std::vector <bool> mask(2000, 0);
		
		mask.assign(2000, 0);
		for (int i = 0; i * k + k < 2000; i += 2) {
			int start = i * k + k;
			mask[start] = 1;
		}
		append_store(bkp1, mask);
		
		mask.assign(2000, 0);
		for (int i = 0; i * k + k + 1 < 2000; i += 2) {
			int start = i * k;
			for (int j = 0; j < k + 1; j++) {
				mask[start + j] = 1;
			}
		}
		append_store(kp1ones, mask);
	}
	
	std::vector <bool> mask(2000, 0);
	for (int i = n * k; i < 2000; i++) {
		mask[i] = 1;
	}
	append_store(80, mask);
	auto tmp = mask;
	std::vector <int> ind_left(n);
	std::iota(ind_left.begin(), ind_left.end(), 0);
	while ((int) ind_left.size() > 1) {
		append_or(0, 0, 80);
		if (ind_left.size() & 1) {
			ind_left.push_back(ind_left.back() + (ind_left[1] - ind_left[0]));
		}
		std::vector <int> next_ind;
		for (int i = 0; i < (int) ind_left.size(); i += 2) {
			next_ind.push_back(ind_left[i]);
		}
		mask.assign(2000, 0);
		for (int i = 1; i < (int) ind_left.size(); i += 2) {
			for (int j = ind_left[i] * k; j < ind_left[i] * k + k; j++) {
				mask[j] = 1;
			}
		}
		append_store(79, mask);
		mask.assign(2000, 0);
		for (int i = 0; i < (int) ind_left.size(); i += 2) {
			for (int j = ind_left[i] * k; j < ind_left[i] * k + k; j++) {
				mask[j] = 1;
			}
		}
		append_store(78, mask);
		append_and(1, 0, 79);
		append_right(1, 1, (ind_left[1] - ind_left[0]) * k);
		append_and(0, 78, 0);
		compare_even_pos();
		//append_right(2, 2, 1);
		int left = k - 1 + 1;
		int sofar = 1;
		while (left) {
			if (sofar <= left) {
				append_right(3, 2, sofar);
				append_or(2, 2, 3);
				left -= sofar;
				sofar <<= 1;
			} else {
				append_right(3, 2, left);
				append_or(2, 2, 3);
				break;
			}
		}
		append_and(3, 2, 0);
		append_not(2, 2);
		append_and(4, 2, 1);
		append_or(0, 3, 4);
		// now register 3 has value of greater number between the two compared values
		//append_xor(4, 3, 0);
		//append_xor(0, 4, 1);
		ind_left = next_ind;
	}
}

// 7 + n * 22 queries worst case (n = 100, k = 10 -> 2207)
void construct_instructions(int _s, int _n, int _k, int _q) {
	s = _s, n = _n, k = _k, q = _q;
	if (!s) {
		solve_s0();
		return;
	}
	prepare_masks();
	for (int i = 0; i < n; i++) {
		if (i & 1) {
			go1();
		} else {
			go0();
		}
	}
}

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