oj.uz

Submission #507937

# Submission time Handle Problem Language Result Execution time Memory
507937 2022-01-13T04:41:36 Z ITO Bit Shift Registers (IOI21_registers) C++17
100 / 100
 2 ms 588 KB 
#include "registers.h"
#include <bits/stdc++.h>
using namespace std;
vector<bool> fillend(2000), nummask(2000), add1(2000);
void construct_instructions(int s, int n, int k, int q) {
	for (int i = n * k; i < 2000; i++) {
		fillend[i] = 1;
	}
	for (int i = 0; i < 2000; i += 2 * k) {
		for (int j = i; j < i + k && j < 2000; j++) {
			nummask[j] = 1;
		}
		add1[i] = 1;
	}
	if (s == 0) {
		append_store(1, fillend);
		append_store(3, nummask);
		append_store(4, add1);
		append_or(0, 0, 1); // fill end with max
		append_right(10, 0, k); // position numbers
		append_and(0, 0, 3);
		int i = (n + 1) / 2;
		while(1) {
			append_not(11, 10);
			append_and(11, 11, 3);
			append_add(11, 11, 4);
			append_add(11, 0, 11); // 0 smaller when no overflow
			append_right(11, 11, k); // focus on overflow
			append_and(11, 11, 3); // clear garbage
			int j = 1;
			while (j < k) {
				append_left(12, 11, min(j, k - j));
				append_or(11, 11, 12);
				j *= 2;
			} // 10 smaller mask
			append_xor(12, 11, 3); // 0 smaller mask
			append_and(10, 10, 11);
			append_and(0, 0, 12);
			append_or(0, 0, 10);
			if (i == 1) {
				break;
			}
			i = (i + 1) / 2;
			append_right(10, 0, i * 2 * k);
		}
	} else {
		append_store(1, fillend);
		append_store(3, nummask);
		append_store(4, add1);
		append_or(0, 0, 1); // fill end with max
		append_right(10, 0, k); // position numbers
		append_and(0, 0, 3);
		for (int i = n / 2; i < n; i++) {
			append_not(11, 10);
			append_and(11, 11, 3);
			append_add(11, 11, 4);
			append_add(11, 0, 11); // 0 smaller when no overflow
			append_right(11, 11, k); // focus on overflow
			append_and(11, 11, 3); // clear garbage
			int j = 1;
			while (j < k) {
				append_left(12, 11, min(j, k - j));
				append_or(11, 11, 12);
				j *= 2;
			} // 10 smaller mask
			append_xor(12, 11, 3); // 0 smaller mask
			append_and(20, 0, 12);
			append_and(21, 0, 11);
			append_and(30, 10, 11);
			append_and(31, 10, 12);
			append_or(0, 20, 30);
			append_or(21, 21, 31);
			append_left(10, 21, k * 2);
			append_not(11, 10);
			append_and(11, 11, 3);
			append_add(11, 11, 4);
			append_add(11, 0, 11); // 0 smaller when no overflow
			append_right(11, 11, k); // focus on overflow
			append_and(11, 11, 3); // clear garbage
			j = 1;
			while (j < k) {
				append_left(12, 11, min(j, k - j));
				append_or(11, 11, 12);
				j *= 2;
			} // 10 smaller mask
			append_xor(12, 11, 3); // 0 smaller mask
			append_and(20, 0, 12);
			append_and(21, 0, 11);
			append_and(30, 10, 11);
			append_and(31, 10, 12);
			append_or(0, 21, 31);
			append_or(21, 20, 30);
			if (i == n - 1) {
				append_right(10, 21, k);
				append_or(0, 0, 10);
			} else {
				append_right(10, 21, k * 2);
			}
		}
	}
}

Subtask #1
10.0 / 10.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 284 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 292 KB Output is correct
4 Correct 1 ms 276 KB Output is correct

Subtask #4
25.0 / 25.0

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

Subtask #5
13.0 / 13.0

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

Subtask #6
29.0 / 29.0

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