Submission #599758

#	Time	Username	Problem	Language	Result	Execution time	Memory
599758		idiot123	Bit Shift Registers (IOI21_registers)	C++17	64 / 100	2 ms	596 KiB

registers

#include "registers.h"

using namespace std;

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

void construct_instructions(int s, int n, int k, int q) {
	//first we need to make space between numbers
	//if(s == 1){
		vector<bool> v(b, false);
		//oddReg and evenReg can be used to separate numbers on odd and even positions
		int oddReg = 99;
		for(int i = 1; i < n; i+=2){
			for(int j = k*i; j < k*i + k; j++)v[j] = 1;
		}
		append_store(oddReg, v);
		for(int i = 0; i < b; i++)v[i] = 0;
		for(int i = 0; i < n; i+=2){
			for(int j = k*i; j < k*(i+1); j++)v[j] = 1;
		}
		int evenReg = 98;
		append_store(evenReg, v);
		int aReg = 1; int bReg = 2;
		append_and(aReg, evenReg, 0);
		append_and(bReg, oddReg, 0);
		append_right(bReg, bReg, k);
		int evenSwapRange = 96; int oddSwapRange = 97;
		append_right(oddReg, oddReg, k);
		append_and(evenSwapRange, oddReg, evenReg);
		append_left(oddReg, oddReg, 2*k);
		append_and(oddSwapRange, oddReg, evenReg);
		append_right(oddReg, oddReg, k);
		int c, d, e, f; c = 3; d = 4; e = 5; f= 6;
		int swap = 7; int antiSwap = 8;
		int signReg = 9; int negateReg = 10;
		int addReg = 11;
		for(int i = 0; i < b; i++)v[i] = 0;
		for(int i = 0; i < n; i+= 2){
			v[k*i + k] = 1;
		}
		append_store(signReg, v);
		append_right(addReg, signReg, k);
		append_or(negateReg, signReg, evenReg);
		for(int i = 0; i < n; i++){
			if(i % 2 == 0){
				if(k == 1){
					append_not(swap, bReg);
					append_and(swap, swap, aReg);
				}else{
					append_xor(swap, aReg, negateReg);
					append_add(swap, swap, addReg);
					append_add(swap, swap, bReg);
					append_and(swap, swap, signReg);
					//na tym etapie na pojedynczych bitach jest znak, trzeba go rozmazac o k pozycji w prawo
					int xd = 1;
					while(2 * xd <= k + 1){
						append_right(antiSwap, swap, xd);
						append_or(swap, swap, antiSwap);
						xd *= 2;
					}
					if(xd < k + 1){
						append_right(antiSwap, swap, k + 1 - xd);
						append_or(swap, swap, antiSwap);
					}
					//swap powinien byc juz gotowy
				}
				append_and(swap, swap, evenSwapRange);//ograniczamy zakres swapa
				append_not(antiSwap, swap);
				append_and(c, aReg, antiSwap);
				append_and(d, aReg, swap);
				append_and(e, bReg, antiSwap);
				append_and(f, bReg, swap);
				
				append_add(aReg, c, f);
				append_add(bReg, d, e);
			}else{
				append_left(bReg, bReg, 2*k);
				
				if(k == 1){
					append_not(swap, aReg);
					append_and(swap, swap, bReg);
				}else{
					append_xor(swap, bReg, negateReg);
					append_add(swap, swap, addReg);
					append_add(swap, swap, aReg);
					append_and(swap, swap, signReg);
					//na tym etapie na pojedynczych bitach jest znak, trzeba go rozmazac o k pozycji w prawo
					int xd = 1;
					while(2 * xd <= k + 1){
						append_right(antiSwap, swap, xd);
						append_or(swap, swap, antiSwap);
						xd *= 2;
					}
					if(xd < k + 1){
						append_right(antiSwap, swap, k + 1 - xd);
						append_or(swap, swap, antiSwap);
					}
					//swap powinien byc juz gotowy
				}
				append_and(swap, swap, oddSwapRange);//ograniczamy zakres swapa
				append_not(antiSwap, swap);
				append_and(c, aReg, antiSwap);
				append_and(d, aReg, swap);
				append_and(e, bReg, antiSwap);
				append_and(f, bReg, swap);
				
				append_add(aReg, c, f);
				append_add(bReg, d, e);
				
				append_right(bReg, bReg, 2*k);
			}
		}
		append_left(bReg, bReg, k);
		append_add(0, aReg, bReg);
	//}
}

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