oj.uz

Submission #979653

# Submission time Handle Problem Language Result Execution time Memory
979653 2024-05-11T09:28:04 Z canadavid1 Bit Shift Registers (IOI21_registers) C++17
100 / 100
 1 ms 644 KB 
#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,
	MASK,
	LO,
	HI
};

void setup_registers(int n, int k,int _n,int s=1)
{
	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;
	if(s){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);}
	for(int i = 0; i < b; i++) v[i] = i < k*_n;
	append_store(MASK,v);
}
void sort_pair(int n, int k,int ev=EVEN,int od=ODD,bool rev=false) // 16 instrs
{
	append_and(ra,buf,ev);
	append_and(rb,buf,od);
	append_right(rb,rb,k);
	if(rev) append_not(ra,ra);
	else 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);
	if(!rev) 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,n,s);
	if(s==0 && n > 2)
	{
		append_xor(buf,buf,MASK);
		while(n > 1)
		{
			// append_print(buf);
			sort_pair(N,k,EVEN,ODD,true); // 17
			// append_print(buf);
			if(n==2) break;
			std::vector<bool> v(b,0);
			for(int i = 0; i < (n+1)/2; i++) for(int j = 0; j < 2*k; j++) v[i*2*k+j] = i >= (n+3)/4 && j < k;
			append_store(HI,v);
			for(int i = 0; i < (n+1)/2; i++) for(int j = 0; j < 2*k; j++) v[i*2*k+j] = i < (n+3)/4 && j < k;
			n = (n+1)/2;
			append_store(LO,v);
			append_and(ra,buf,HI);
			append_and(buf,buf,LO);
			// append_print(buf);
			// append_print(ra);
			append_right(ra,ra,((n+1)/2)*2*k-k);
			append_or(buf,buf,ra);
			// 23
		}
		append_xor(buf,buf,MASK);
		return;
	}
	// even-odd sort
	for(int i = 0; i < N; i+=2)
	{
		// // append_print(buf);
		sort_pair(N,k);
		// // append_print(buf);
		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);
	return;
	
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 380 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #6
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 644 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct