oj.uz

Submission #636712

# Submission time Handle Problem Language Result Execution time Memory
636712 2022-08-30T00:32:28 Z imeimi2000 Bit Shift Registers (IOI21_registers) C++17
100 / 100
 2 ms 596 KB 
#include "registers.h"

using namespace std;

const int B = 2000;

void solve1(int n, int k, bool first = true) {
	if (n == 1) return;
	const int MASK = 97;
	const int MSB = 98;
	const int ONE = 99;
	vector<bool> mask, msb, one(B, false), fill;
	one[0] = true;
	mask.reserve(B);
	msb.reserve(B);
	fill.reserve(B);
	for (int i = 0; i < B; ++i) {
		mask.push_back(i / k % 2 == 0);
		msb.push_back(!mask[i] && i % k == 0);
		fill.push_back(n * k <= i);
	}
	if (first) {
		if (n > 2) {
			append_store(99, fill);
			append_add(0, 0, 99);
		}
		append_store(ONE, one);
	}
	append_store(MASK, mask);
	append_store(MSB, msb);

	append_or(3, 0, MSB);

	append_right(2, 0, k);
	append_and(2, 2, MASK);
	append_not(4, 2);
	append_add(4, 4, ONE);

	append_add(3, 3, 4);
	append_and(3, 3, MSB);
	append_right(4, 3, k);
	append_not(4, 4);
	append_add(4, 4, ONE);
	append_add(3, 3, 4);
	append_not(4, 3);
	append_and(4, 4, MASK);

	append_and(1, 0, 4);
	append_and(2, 2, 3);
	append_add(0, 1, 2);
	append_print(0);
	solve1((n + 1) / 2, k * 2, false);
}

void solve2(int n, int k) {
	const int FILL = 96;
	const int MASK = 97;
	const int MSB = 98;
	const int ONE = 99;
	vector<bool> mask, msb, one(B, false), fill;
	one[0] = true;
	mask.reserve(B);
	msb.reserve(B);
	fill.reserve(B);
	for (int i = 0; i < B; ++i) {
		mask.push_back(i / k % 2 == 0);
		msb.push_back(!mask[i] && i % k == 0);
		fill.push_back(n * k <= i);
	}
	append_store(FILL, fill);
	append_add(0, 0, FILL);
	append_store(ONE, one);
	append_store(MASK, mask);
	append_store(MSB, msb);
	for (int i = 0; i < n + 5; ++i) {
		if (i & 1) {
			append_left(0, 0, k);
		}
		append_or(1, 0, MSB);
		append_right(2, 0, k);
		append_and(2, 2, MASK);
		append_not(3, 2);
		append_add(3, 3, ONE);
		append_add(3, 1, 3);
		append_and(3, 3, MSB);
		append_right(4, 3, k);
		append_not(4, 4);
		append_add(4, 4, ONE);
		append_add(3, 3, 4);
		append_not(4, 3);
		append_and(1, 0, MASK);
		append_and(0, 1, 4); // first min
		append_and(6, 1, 3); // first max
		append_left(6, 6, k);
		append_add(0, 0, 6);
		append_and(7, 2, 3); // second min
		append_add(0, 0, 7);
		append_and(8, 2, 4); // second max
		append_left(8, 8, k);
		append_add(0, 0, 8);
		if (i & 1) {
			append_right(0, 0, k);
			append_or(0, 0, FILL);
		}
	}
}

void construct_instructions(int s, int n, int k, int q) {
	if (s == 0) solve1(n, k);
	else solve2(n, k);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
25.0 / 25.0

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

Subtask #5
13.0 / 13.0

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

Subtask #6
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct