Submission #640557

#	Time	Username	Problem	Language	Result	Execution time	Memory
640557		Aderfish	Bit Shift Registers (IOI21_registers)	C++17	58 / 100	1 ms	340 KiB

registers

#include "registers.h"
using namespace std;


const int m = 100;
const int b = 2000;

const int one_register = 99;
const int temp_mux = 98;
const int temp_min = 96;

const int bal_odd_mask = 95;
const int unbal_mask = 94;
const int rep_one_mask = 93;
const int ball_even_mask = 92;

//mux, uses temp_mux, c should be full of 1's or 0's, x, y, and c are not written to
void mux(int t, int x, int y, int c){
	append_and(t, x, c);
	append_not(temp_mux, c);
	append_and(temp_mux, temp_mux, y);
	append_or(t, t, temp_mux);
}


// creates a mask with 1's in between l and r, 0 otherwise
vector<bool> mask1(int l, int r){
	vector<bool> res = vector<bool>(b);
	for(int i = 0; i < b; i++){
		if(l <= i && i < r) res[i] = 1;
	}

	return res;
}

void extract(int t, int x, int l, int r){
	append_store(t, mask1(l, r));
	append_and(t, t, x);
}

// i is start intdex, w is width
void extract_shift(int t, int x, int i, int w){
	append_left(t, x, b-w-i);
	append_right(t, t, b-w);
}

vector<bool> even_balanced_mask(int w){
	vector<bool> r(b);
	for(int i = 0; i < b; i++){
		if((i/w)%2 == 0) r[i] = true;
		else r[i] = false;
	}

	return r;
}

vector<bool> odd_balanced_mask(int w){
	vector<bool> r(b);
	for(int i = 0; i < b; i++){
		if((i/w)%2 == 1) r[i] = true;
		else r[i] = false;
	}

	return r;
}

vector<bool> even_unbalanced_mask(int w){
	vector<bool> r(b);
	
	for(int i = 0; i < b; i++){
		int m = i%(2*w);
		if(m < w+1) r[i] = true;
		else r[i] = false;
	}

	return r;
}

vector<bool> repeated_one(int w){
	vector<bool> r(b);
	
	for(int i = 0; i < b; i++){
		int m = i%(2*w);
		if(m == 0) r[i] = true;
		else r[i] = false;
	}

	return r;
}

void construct_instructions(int s, int n, int k, int q) {

	if(s == 0){
		if(k == 1){
			append_store(one_register, mask1(0, 1));
			append_add(0, 0, one_register);
			append_right(0, 0, n);
		}

		// filling the rest of the input with 1's
		append_store(1, mask1(n*k, b));
		append_or(0, 0, 1);

		const int even = 1;
		const int odd = 2;
		const int opposite_and_cond = 3;

		int w = k;
		while(w < n*k){
			append_print(0);

			append_store(ball_even_mask, even_balanced_mask(w));
			append_store(bal_odd_mask, odd_balanced_mask(w));
			append_store(unbal_mask, even_unbalanced_mask(w));
			append_store(rep_one_mask, repeated_one(w));

			// extraction
			append_and(even, ball_even_mask, 0);
			append_and(odd, bal_odd_mask, 0);
			append_right(odd, odd, w);

			// taking the opposite of the extracted nums
			append_xor(opposite_and_cond, odd, unbal_mask);
			append_add(opposite_and_cond, opposite_and_cond, rep_one_mask);

			append_print(opposite_and_cond);

			// adding the 2 halves
			append_add(opposite_and_cond, even, opposite_and_cond);
			append_and(opposite_and_cond, opposite_and_cond, unbal_mask);

			// extracting the most sign bit
			append_right(opposite_and_cond, opposite_and_cond, w);
			append_and(opposite_and_cond, opposite_and_cond, ball_even_mask);
			append_add(opposite_and_cond, opposite_and_cond, ball_even_mask);

			append_print(opposite_and_cond);

			// should not be necessary
			//append_and(opposite_and_cond, opposite_and_cond, ball_even_mask);
			// 1's means odd <= even
			
			mux(0, odd, even, opposite_and_cond);

			w <<= 1;
		}


	}

	append_print(0);

	return;
}

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