oj.uz

Submission #437955

# Submission time Handle Problem Language Result Execution time Memory
437955 2021-06-27T10:33:42 Z galca Bit Shift Registers (IOI21_registers) C++17
58 / 100
 1 ms 204 KB 
#include "registers.h"

void construct_instructions(int s, int n, int k, int q) {
	append_print(0);
	
	std::vector<bool> mask1(2000);
	for (int i = 0; i < 2000; i += 2*k) {
		for (int j = 0; j < k; j++) {
			if (i+j < 2000) mask1[i+j] = true;
		}
		for (int j = 0; j < k; j++) {
			if (i + j + k < 2000) mask1[i + k + j] = false;
		}
	}
	std::vector<bool> one(2000);
	for (int i = 0; i < 2000; i += 2 * k) {
		if (i < 2000) one[i] = true;
		for (int j = 1; j < 2 * k; j++) {
			if (i + j < 2000) one[i + j] = false;
		}
	}
	append_store(2, mask1);
	append_not(3, 2);
	append_store(4, one);

	std::vector<bool> invalid(2000);
	for (int i = 0; i < n * k; i++) {
		invalid[i] = false;
	}
	for (int i = n*k; i < 2000; i++) {
		invalid[i] = true;
	}

	append_store(5, invalid);
	append_or(0, 0, 5);

	int msb = 0x1;
	int logn = 0;
	while (msb < n) {
		msb <<= 1;
		++logn;
	}

	for (int i = 0; i < logn; i++) {
		//append_move(1, 0);
		append_right(1, 0, k*(1 << i));

		append_print(1);

		append_and(0, 0, 2); // reg0 holds a (even)
		append_and(1, 1, 2); // reg1 holds b (odd)
		
		append_print(0);
		append_print(1);

		append_xor(5, 1, 2);
		append_add(5, 5, 4); // reg5 holds -b

		append_print(5);

		append_add(6, 5, 0); // reg6 holds a - b

		append_print(6);

		append_move(7, 0);
		// if a > b, overflow bit is 1
		// if a < b, overflow bit is 0
		append_and(6, 6, 3); // reg6 holds the overflow of a-b
		append_add(6, 6, 3); // reg6 holds ffff if a is the min, 0 otherwise
		append_right(8, 6, k); // reg8 aligns the mask against the val
		append_not(9, 8);

		append_print(8);
		append_print(9);

		// move min to 0
		append_and(10, 7, 8);
		append_and(11, 1, 9);
		append_or(0, 10, 11);
		// move max to 1 - no need for min only
		//append_and(10, 7, 9);
		//append_and(11, 1, 8);
		//append_or(1, 10, 11);
	}
}

Subtask #1
10.0 / 10.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
25.0 / 25.0

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

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Incorrect sorting
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Incorrect sorting
2 Halted 0 ms 0 KB -