Submission #1127934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127934		hmm	Bit Shift Registers (IOI21_registers)	C++20	46 / 100	1 ms	744 KiB

registers

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

void compare(int reg, int mins, int maxes, int n, int k, int odds = 99, int evens = 98, int ones = 97){ // uses registers [80, 86]
	// using register [80, 96] as temporary registers
	
	append_and( 80, reg, evens);
	append_and( 86, reg, odds);
	append_right(86, 86, k);

	append_not(81, 86); //no need to increment as swapping does not matter when equal
	append_and(81, 81, evens);

	append_add(82, 80, 81);

	append_and(82, 82, odds);
	
	int i;
	int a = 82, b = 83;
	for(i = 1; i <= k; i<<=1){
		append_right(b, a, i);
		append_or(b, b, a);
		a ^= b ^= a ^= b;
	}

	append_and(a, a, evens);
	append_not(b, a);

	append_and(84, 80, b);
	append_and(85, 86, a);
	append_or(mins, 84, 85);

	append_and(84, 80, a);
	append_and(85, 86, b);
	append_or(maxes, 84, 85);

}

void comp2(int a, int b, int k, int odds=99, int evens=98){
	append_not(80, b);
	append_and(80, 80, evens);
	append_add(81, 80, a);
	append_and(81, 81, odds);
	int i;
	int x = 81, y = 82;
	append_right(x, x, 1);
	for(i = 1; i < k || i == k && k > 2; i<<=1){
		append_right(y, x, i);
		append_or(y, y, x);
		x ^= y ^= x ^= y;
	}
	append_and(x, x, evens);
	append_not(y, x);

	append_and(83, a, y);
	append_and(84, b, x);

	append_xor(b, b, a);
	append_or(a, 83, 84);
	append_xor(b, b, a);
}

void getmin(int n, int k, int odds=99, int evens=98){
	int i = 0;
	while(1<<i < n) i++;

	append_and( 1, 0, evens);
	append_and( 2, 0, odds);
	append_right(2, 2, k);

	if(n%2 == 1){
		std::vector<bool> v(2000);
		for(int j = (n-1)*k; j < n*k-1; j++) v[j] = 1;
		append_store(3, v);
		append_or(2, 2, 3);
	}

	comp2(1,2,k);
	i--;
	n = (n+1)/2;
	while(n > 1){
		append_right(2, 1, (int) (n/2)*2*k);
	append_print(1);
	append_print(2);

		comp2(1, 2, k);

		n = (n+1)/2;
	}
	append_move(0, 1);

	append_print(1);
	append_print(2);

}

void shuffle(int reg, int next, int n, int k, int temp0, int tempmax, int tempmin, int templast, int temp = 87){

	compare(reg, tempmin, tempmax, n, k);
	append_left(temp0, tempmin, 2000-k);
	append_right(temp0, temp0, 2000-k);
	append_right(templast, tempmax, k*(n-2));
	append_left(templast, templast, k*(n-1));

	append_left(tempmax, tempmax, 2000 - k*(n-2));
	append_right(tempmax, tempmax, 2000 - k*(n-2));
	append_right(tempmin, tempmin, k);

	append_or(temp, tempmin, tempmax);

	compare(temp, tempmin, tempmax, n-2, k);

	append_left(tempmin, tempmin, 1*k);
	append_left(tempmax, tempmax, 2*k);

	append_or(next, tempmin, tempmax);
	append_or(next, next, temp0);
	append_or(next, next, templast);
}

void construct_instructions(int s, int n, int k, int q) {
	if(n < 2) return;

	std::vector<bool> odds(2000), evens(2000), ones(2000);
	for(int i = 0; i < n*k; i++){
		if( (i/k)%2 == 0 ){
			evens[i] = 1;
		} else {
			odds[i] = 1;
		}
		if( i%k == 0 ) ones[i] = 1;
	}

	append_store(99, odds);
	append_store(98, evens);
//	append_store(97, ones);


	if(s == 1){
		for(int i=0; i<n; i++){
			shuffle(0, 0, n, k, 1, 2, 3, 4);
		}
	}

	if(s == 0){
		getmin(n, k);
	}

}

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