oj.uz

Submission #979564

# Submission time Handle Problem Language Result Execution time Memory
979564 2024-05-11T07:50:11 Z canadavid1 Bit Shift Registers (IOI21_registers) C++17
75 / 100
 1 ms 604 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,
};

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.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 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 604 KB Output is correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Wrong answer detected in grader
2 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.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

Subtask #6
29.0 / 29.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 604 KB Output is correct
4 Correct 1 ms 604 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