Submission #819359

#	Time	Username	Problem	Language	Result	Execution time	Memory
819359		HamletPetrosyan	Bit Shift Registers (IOI21_registers)	C++17	10 / 100	1 ms	340 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){
		hn = (hn + 1) / 2;	
		for(int i = 0; i < B; i++){
			v98[i] = v97[i] = v96[i] = v95[i] = v94[i] = 0;
		}

		bool cnt = 0;
		int g = B;
		for(int i = 0; i < n; i++){
			if(usd[i]) continue;
			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(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++) v97[j] = 1;
				v95[i * k] = 1;
				v94[(i + 1) * k] = 1;
			}
			cnt = !cnt;
		}

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

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

		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
	}
}

void get_sorted(int n, int k){
	vector<bool> stv(k);
}

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: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 25
• Subtask 5: 0 / 13
• Subtask 6: 0 / 29