oj.uz

Submission #775478

# Submission time Handle Problem Language Result Execution time Memory
775478 2023-07-06T12:32:07 Z SanguineChameleon Bit Shift Registers (IOI21_registers) C++17
100 / 100
 1 ms 596 KB 
#include "registers.h"
#include <bits/stdc++.h>
using namespace std;

const int ONE = 99;
const int CARRY = 98;
const int EVEN = 97;
const int ODD_ON = 96;
const int ODD_OFF = 95;
const int FIRST = 94;
const int TMP1 = 93;
const int TMP2 = 92;
int S, N, K;

void order(int A, int B) {
	append_not(TMP1, A);
	append_add(TMP1, TMP1, B);
	append_add(TMP1, TMP1, ONE);
	append_xor(TMP1, TMP1, A);
	append_xor(TMP1, TMP1, B);
	append_and(TMP1, TMP1, CARRY);
	append_right(TMP2, TMP1, K);
	append_not(TMP2, TMP2);
	append_add(TMP1, TMP1, TMP2);
	append_add(TMP1, TMP1, ONE);
	append_move(TMP2, A);
	append_xor(TMP2, TMP2, B);
	append_and(TMP2, TMP2, TMP1);
	append_xor(A, A, TMP2);
	append_xor(B, B, TMP2);
}

void construct_instructions(int _S, int _N, int _K, int Q) {
	S = _S;
	N = _N;
	K = _K;
	{
		vector<bool> bits(2000);
		bits[0] = 1;
		append_store(ONE, bits);
	}
	if (S == 0) {
		{
			vector<bool> bits(2000);
			for (int i = 1; i <= N; i++) {
				bits[i * K] = 1;
			}
			append_store(CARRY, bits);
		}
		while (N > 1) {
			append_right(1, 0, (N >> 1) * K);
			order(0, 1);
			N = (N + 1) >> 1;
		}
	}
	else {
		int newN = max(N, 4);
		if (newN & 1) {
			newN++;
		}
		{
			vector<bool> bits(2000);
			for (int i = N * K; i < newN * K; i++) {
				bits[i] = 1;
			}
			append_store(TMP1, bits);
			append_or(0, 0, TMP1);
		}
		N = newN;
		{
			vector<bool> bits(2000);
			for (int i = 1; i <= N; i++) {
				bits[i * K] = 1;
			}
			append_store(CARRY, bits);
		}
		{
			vector<bool> bits(2000);
			for (int i = 0; i < (N >> 1) * K; i++) {
				bits[i] = 1;
			}
			append_store(EVEN, bits);
		}
		{
			vector<bool> bits(2000);
			for (int i = ((N >> 1) - 1) * K; i < ((N >> 1) + 1) * K; i++) {
				bits[i] = 1;
			}
			append_store(ODD_ON, bits);
		}
		{
			vector<bool> bits(2000);
			for (int i = 0; i < ((N >> 1) - 1) * K; i++) {
				bits[i] = 1;
			}
			append_store(ODD_OFF, bits);
		}
		{
			vector<bool> bits(2000);
			for (int i = 0; i < K; i++) {
				bits[i] = 1;
			}
			append_store(FIRST, bits);
		}
		append_move(1, 0);
		for (int iter = 0; iter < N; iter++) {
			if (iter & 1) {
				append_right(2, 1, (N >> 1) * K);
				append_and(1, 1, EVEN);
				order(2, 1);
				append_left(2, 2, (N >> 1) * K);
				append_add(1, 1, 2);
			}
			else {
				append_right(2, 1, ((N >> 1) + 1) * K);
				append_or(2, 2, ODD_ON);
				order(1, 2);
				append_and(2, 2, ODD_OFF);
				append_left(2, 2, ((N >> 1) + 1) * K);
				append_add(1, 1, 2);
			}
		}
		append_xor(0, 0, 0);
		for (int i = 0; i < N; i++) {
			int pos = (i >> 1) + ((i & 1) ? 0 : (N >> 1));
			append_right(TMP1, 1, pos * K);
			append_and(TMP1, TMP1, FIRST);
			append_left(TMP1, TMP1, i * K);
			append_add(0, 0, TMP1);
		}
	}
}

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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #6
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 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