Submission #979564

#	Time	Username	Problem	Language	Result	Execution time	Memory
979564		canadavid1	Bit Shift Registers (IOI21_registers)	C++17	75 / 100	1 ms	604 KiB

registers

#include "registers.h"
// void append_move(int t, int x);
// void append_store(int t, std::vector<bool> v);
// void append_and(int t, int x, int y);
// void append_or(int t, int x, int y);
// void append_xor(int t, int x, int y);
// void append_not(int t, int x);
// void append_left(int t, int x, int s);
// void append_right(int t, int x, int s);
// void append_add(int t, int x, int y);
// void append_print(int t);
// void construct_instructions(int s, int n, int k, int q);

constexpr int b = 2000;
enum
{
	buf=0,
	ra,
	rb,
	rc,
	rd,
	t,
	EVEN,
	ODD,
	EDGE,
	EVEN2,
	ODD2,
	TOP,
	NTOP,
	NEDGE,
};

void setup_registers(int n, int k)
{
	std::vector<bool> v(b);
	for(int i = 0; i < n; i++) for(int j = 0; j < k; j++) v[i*k+j] = i%2;
	append_store(ODD,v);
	append_right(EVEN,ODD,k);
	if(n==2) return;
	for(int i = 0; i < n; i++) for(int j = 0; j < k; j++) v[i*k+j] = i==0 || i == n-1;
	append_store(EDGE,v);
	append_not(NEDGE,EDGE);
	v.assign(b,0);
	for(int i = 0; i < n-1; i++) for(int j = 0; j < k; j++) v[i*k+j] = i%2;
	append_store(ODD2,v);
	append_right(EVEN2,ODD2,k);
	append_not(NTOP,TOP);

}
void sort_pair(int n, int k,int ev=EVEN,int od=ODD) // 16 instrs
{
	append_and(ra,buf,ev);
	append_and(rb,buf,od);
	append_right(rb,rb,k);
	append_not(rb,rb);
	append_add(rb,rb,ra);
	append_and(rb,rb,od); // 2 now 0C0C0C0C, C = 1s means to not swap
	append_right(ra,rb,k);
	append_or(ra,ra,rb); // 1 now ccCCccCC
	append_and(rc,buf,ra); // the part that is to keep

	append_xor(rb,rb,od); // 2 now 0C0C, C = 1s means to swap
	append_and(rd,rb,buf);
	append_left(buf,buf,k);
	append_right(rd,rd,k);
	append_and(buf,rb,buf);
	append_or(buf,buf,rc);
	append_or(buf,buf,rd);
}

void construct_instructions(int s, int n, int k, int q) {
	int N = 2*((n+1)/2);
	setup_registers(N,k);
	// even-odd sort
	for(int i = 0; i < N; i+=2)
	{
		sort_pair(N,k);
		if(n==2) break;
		append_and(t,buf,EDGE);
		append_and(buf,buf,NEDGE);
		append_right(buf,buf,k);
		sort_pair(N,k,EVEN2,ODD2);
		append_left(buf,buf,k);
		append_or(buf,buf,t);
	}
	if(N>n) append_right(buf,buf,(N-n)*k);
}

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