oj.uz

Submission #788796

# Submission time Handle Problem Language Result Execution time Memory
788796 2023-07-20T15:57:17 Z thimote75 Bit Shift Registers (IOI21_registers) C++17
22 / 100
 1 ms 432 KB 
#include "registers.h"

#include <bits/stdc++.h>

using namespace std;

using bdata = vector<bool>;
using idata = vector<int>;

static const int m = 100;
static const int b = 2000;
static const int VB = 2000;

const int MAX_REG = m - 1;
const int XOR_REG = m - 2;
const int SUM_REG = m - 3;
const int EXT_REG = m - 4;
const int SAV_REG = m - 5;
const int ONE_REG = m - 6;

void init_min (int k) {
	bdata mask(b, false);
	for (int i = 0; i < b; i += 2 * k + 1)
		for (int j = 0; j < 2 * k; j ++)
			mask[i + j] = true;
	
	append_store( MAX_REG, mask );

	bdata one (b, false);
	for (int i = 0; i < b; i += 2 * k + 1)
		one[i] = true;

	append_store( ONE_REG, one );
}
void append_min (int k, int f, int s, int target) {
	bdata one (b, false); one[0] = true;
	append_move(SUM_REG, ONE_REG);
	append_xor( XOR_REG, s, MAX_REG );
	append_add( SUM_REG, f, SUM_REG );
	append_add( SUM_REG, XOR_REG, SUM_REG );
	append_right( SUM_REG, SUM_REG, k );
	append_and ( XOR_REG, SUM_REG, f );
	append_not ( SUM_REG, SUM_REG );
	append_and ( SUM_REG, SUM_REG, s );
	append_add ( target, SUM_REG, XOR_REG );
}

void extract (int target, int sizes, int index) {
	append_move(EXT_REG, 0);
	int l = sizes * index;

	append_right(EXT_REG, EXT_REG, l);
	int del = b - sizes;
	append_left (EXT_REG, EXT_REG, del);
	append_right(EXT_REG, EXT_REG, del);
	append_move (target, EXT_REG);
}

void run_min (int a, int b, int sl, int sr, int k) {
	append_min(k, a, b, a);
}

void find_min (int a, int b, int sizea, int sizeb, int k) {
	//append_print(7);
	//append_print(a);
	//append_print(b);

	run_min(a, b, sizea, sizeb, k);

	while (sizea != 1 || sizeb != 1) {
		//append_print(8);
		//append_print(a);
		//append_print(b);
		bdata fill_b(VB, false);

		sizeb = sizea >> 1;
		sizea = sizea - sizeb;

		for (int i = (2 * k + 1) * sizeb; i < (2 * k + 1) * sizea; i += 2 * k + 1) {
			for (int j = 0; j < k; j ++)
				fill_b[j + i] = true;
		}

		append_move (b, a);
		append_right(b, b, sizea * (2 * k + 1));

		append_store(SAV_REG, fill_b);
		append_or   (b, b, SAV_REG);

		//append_print(7);
		//append_print(a);
		//append_print(b);
		run_min(a, b, sizea, sizeb, k);
	}
}

void construct_instructions(int s, int n, int k, int q) {
	assert(s == 0);
	init_min(k);

	bdata local_mask (b, true);
	for (int i = 0; i < k * n; i ++) local_mask[i] = false;
	append_store(SAV_REG, local_mask);
	append_or(0, 0, SAV_REG);
	n = 100;
	
	for (int i = 0; i < n; i ++) {
		extract(5, k, i);
		int gamma = (2 * k + 1) * (i % 25);
		append_left (5, 5, gamma);
		append_or (i / 25 + 1, i / 25 + 1, 5);
	}

	find_min(1, 2, 25, 25, k);
	find_min(3, 4, 25, 25, k);
	append_min(k, 1, 3, 0);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0.0 / 11.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
0.0 / 25.0

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

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -