Submission #819513

#	Time	Username	Problem	Language	Result	Execution time	Memory
819513		HamletPetrosyan	Bit Shift Registers (IOI21_registers)	C++17	100 / 100	1 ms	588 KiB

registers

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

const int M = 100, B = 2000;

// 99 - zero
// 98 - pair 2nd
// 97 - pair 1st
// 96 - 0 cleaner
// 95 - ones for the pairs
// 94 - checker ones

// 1 - pair 1st
// 2 - pair 2nd

// 3 - not pair 2nd (xor with ones)
// 4 - 3 + ones
// 5 - 4 + 1

// 6 - 5 & 94
// 7 - 6 >> k
// 8 - 7 + 97
// 9 - 8 & 97
// 10 - 9 ^ 97

// 11 - 1 & 9
// 12 - 2 & 10

void get_min(int n, int k){
	int hn = n;
	vector<bool> v98(B), v97(B), v96(B), v95(B), v94(B), usd(n);
	while(hn - 1){	
		for(int i = 0; i < B; i++){
			v98[i] = v97[i] = v96[i] = v95[i] = v94[i] = 0;
		}

		bool cnt = 0;
		int g = B, cc = 0;
		for(int i = 0; i < n; i++){
			if(usd[i]) continue;
			cc++;
			if(cnt){
				for(int j = i * k; j < (i + 1) * k; j++) v98[j] = 1;
				usd[i] = 1;
				g = min(g, i * k);
			}
			else if(cc == hn){
				for(int j = i * k; j < (i + 1) * k; j++) v96[j] = 1;
			}
			else {
				for(int j = i * k; j < (i + 1) * k; j++) v97[j] = 1;
				v95[i * k] = 1;
				v94[(i + 1) * k] = 1;
			}
			cnt = !cnt;
		}
		hn = (hn + 1) / 2;

		append_store(98, v98);														// <-------- 1
		append_print(98);
		append_store(97, v97);														// <-------- 2
		append_print(97);
//		append_store(96, v96); 
		append_store(95, v95);														// <-------- 3
		append_print(95);
		append_store(94, v94);														// <-------- 4
		append_print(94);

		append_and(1, 0, 97);														// <-------- 5
		append_and(2, 0, 98);														// <-------- 6
		append_right(2, 2, g);														// <-------- 7
//		append_and(0, 0, 96);
		append_xor(0, 0, 1);														// <-------- 8
		
		append_xor(3, 2, 97);														// <-------- 9
		append_add(4, 3, 95);														// <-------- 10
		append_add(5, 4, 1);														// <-------- 11

		append_and(6, 5, 94);														// <-------- 12
		append_right(7, 6, k);														// <-------- 13
		append_add(8, 7, 97);														// <-------- 14
		append_and(9, 8, 97);														// <-------- 15
		append_xor(10, 9, 97);														// <-------- 16

		append_and(11, 1, 9);														// <-------- 17
		append_and(12, 2, 10);														// <-------- 18

		append_add(0, 0, 11);														// <-------- 19
		append_add(0, 0, 12);														// <-------- 20
		append_print(0);
	}
}

// 99 - zero

// the 1st swap
// 98 - pair 1st  
// 97 - pair 2nd
// 96 - 0 cleaner
// 95 - ones for the pairs
// 94 - checker ones

// the 2nd swap
// 93 - pair 1st
// 92 - pair 2nd
// 91 - 0 cleaner
// 90 - ones for the pairs
// 89 - checker ones

// 1 - pair 1st
// 2 - pair 2nd

// 3 - 2 ^ 9(8|3)
// 4 - 3 + 9(5|0)
// 5 - 1 + 4

// 6 - 5 & (94|89)
// 7 - 6 >> k
// 8 - 7 + 9(8|3)
// 9 - 8 & 9(8|3)
// 10 - 9 ^ 9(8|3)

// 11 - 1 & 9
// 12 - 2 & 10


void get_sorted(int n, int k){
	int hn = n;
	vector<bool> v98(B), v97(B), v96(B), v95(B), v94(B);
	vector<bool> v93(B), v92(B), v91(B), v90(B), v89(B);
	
	bool cnt = 0;
	for(int i = 0; i < n; i++){
		if(cnt){
			for(int j = i * k; j < (i + 1) * k; j++) v97[j] = 1;
		}
		else if(i == n - 1){
			for(int j = i * k; j < (i + 1) * k; j++) v96[j] = 1;
		}
		else {
			for(int j = i * k; j < (i + 1) * k; j++) v98[j] = 1;
			v95[i * k] = 1;
			v94[(i + 1) * k] = 1;
		}
		cnt = !cnt;
	}

	cnt = 0;
	for(int j = 0; j < k; j++) v91[j] = 1;
	for(int i = 1; i < n; i++){
		if(cnt){
			for(int j = i * k; j < (i + 1) * k; j++) v92[j] = 1;
		}
		else if(i == n - 1){
			for(int j = i * k; j < (i + 1) * k; j++) v91[j] = 1;
		}
		else {
			for(int j = i * k; j < (i + 1) * k; j++) v93[j] = 1;
			v90[i * k] = 1;
			v89[(i + 1) * k] = 1;
		}
		cnt = !cnt;
	}

	append_store(98, v98);
	append_store(97, v97);
	append_store(96, v96);
	append_store(95, v95);
	append_store(94, v94);
	///
	append_store(93, v93);
	append_store(92, v92);
	append_store(91, v91);
	append_store(90, v90);
	append_store(89, v89);

	for(int z = 0; z < hn; z++){
		if(z % 2 != hn % 2){
			append_and(1, 0, 98);
			append_and(2, 0, 97);
			append_right(2, 2, k);

			append_and(0, 0, 96);

			append_xor(3, 2, 98);
			append_add(4, 3, 95);
			append_add(5, 1, 4);

			append_and(6, 5, 94);
			append_right(7, 6, k);
			append_add(8, 7, 98);
			append_and(9, 8, 98);
			append_xor(10, 9, 98);

			append_and(11, 1, 9);
			append_and(12, 2, 10);

			append_add(0, 0, 11);
			append_add(0, 0, 12);

			append_and(11, 1, 10);
			append_and(12, 2, 9);
			append_left(11, 11, k);
			append_left(12, 12, k);

			append_add(0, 0, 11);
			append_add(0, 0, 12);
		}
		else {
			append_and(1, 0, 93);
			append_and(2, 0, 92);
			append_right(2, 2, k);
		
			append_and(0, 0, 91);

			append_xor(3, 2, 93);
			append_add(4, 3, 90);
			append_add(5, 1, 4);

			append_and(6, 5, 89);
			append_right(7, 6, k);
			append_add(8, 7, 93);
			append_and(9, 8, 93);
			append_xor(10, 9, 93);

			append_and(11, 1, 9);
			append_and(12, 2, 10);

			append_add(0, 0, 11);
			append_add(0, 0, 12);

			append_and(11, 1, 10);
			append_and(12, 2, 9);
			append_left(11, 11, k);
			append_left(12, 12, k);

			append_add(0, 0, 11);
			append_add(0, 0, 12);
		}
		append_print(0);
	}
}

void construct_instructions(int s, int n, int k, int q) {
	if(s) get_sorted(n, k);
	else get_min(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