oj.uz

답안 #492711

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
492711 2021-12-08T13:24:29 Z altalk 레지스터 (IOI21_registers) C++17
89 / 100
 2 ms 460 KB 
#include "registers.h"
#include <vector>
#include <iostream>
#define loop(a, b) for(int a = 0; a < b; a++)

constexpr int TASK_MIN = 0;
constexpr int TASK_SORT = 1;


constexpr int BIT_COUNT = 2000;

constexpr int REGISTER_1 = 99;
constexpr int REGISTER_2K = 98;
constexpr int REGISTER_C = 97;
constexpr int REGISTER_EXTRA = 96;

constexpr int REGISTER_IO = 0;
constexpr int REGISTER_A = 1;
constexpr int REGISTER_B = 2;


void sortPrepare(int s, int n, int k, int q) {
	// constants
	std::vector<bool> gen_1(BIT_COUNT);
	loop(a, n/2 + 1) gen_1[(a+1) * (2*k) - 1] = 1;
	append_store(REGISTER_1, gen_1);

	std::vector<bool> gen_2k(BIT_COUNT);
	loop(a, n/2 + 1) loop(b, k) gen_2k[(a+1) * (2*k) - (b+1)] = 1;
	append_store(REGISTER_2K, gen_2k);

	std::vector<bool> gen_c(BIT_COUNT);
	loop(a, n/2 + 1) gen_c[(a+1) * (2*k) - k] = 1;
	append_store(REGISTER_C, gen_c);

	std::vector<bool> gen_extra(BIT_COUNT);
	loop(a, 2*k) gen_extra[n * k + a] = 1;
	append_store(REGISTER_EXTRA, gen_extra);

	// extra char
	append_or(REGISTER_IO, REGISTER_IO, REGISTER_EXTRA);

	// shift the A
	append_left(REGISTER_A, REGISTER_IO, k);

	// mask both A and B
	append_and(REGISTER_B, REGISTER_IO, REGISTER_2K);
	append_and(REGISTER_A, REGISTER_A, REGISTER_2K);

	
}

void sortSmaller(int s, int n, int k, int q, int REGISTER_SMALL, int REGISTER_BIG) {
	constexpr int REGISTER_NB = 3;
	append_not(REGISTER_NB, REGISTER_B);
	append_and(REGISTER_NB, REGISTER_NB, REGISTER_2K);

	constexpr int REGISTER_SUM = 4;
	append_add(REGISTER_SUM, REGISTER_A, REGISTER_NB);

	constexpr int REGISTER_SUM_CARRY = 5;
	append_right(REGISTER_SUM_CARRY, REGISTER_SUM, k);
	append_and(REGISTER_SUM_CARRY, REGISTER_SUM_CARRY, REGISTER_C);

	constexpr int REGISTER_MASK2 = 7;
	append_add(REGISTER_MASK2, REGISTER_SUM_CARRY, REGISTER_2K);
	append_and(REGISTER_MASK2, REGISTER_MASK2, REGISTER_2K);

	constexpr int REGISTER_MASK1 = 6;
	append_not(REGISTER_MASK1, REGISTER_MASK2);

	constexpr int REGISTER_PARTA1 = 8;
	constexpr int REGISTER_PARTA2 = 9;
	constexpr int REGISTER_PARTB2 = 10;
	constexpr int REGISTER_PARTB1 = 11;
	append_and(REGISTER_PARTA1, REGISTER_A, REGISTER_MASK1);
	append_and(REGISTER_PARTA2, REGISTER_A, REGISTER_MASK2);
	append_and(REGISTER_PARTB2, REGISTER_B, REGISTER_MASK2);
	append_and(REGISTER_PARTB1, REGISTER_B, REGISTER_MASK1);

	append_or(REGISTER_BIG, REGISTER_PARTA1, REGISTER_PARTB2);
	append_or(REGISTER_SMALL, REGISTER_PARTA2, REGISTER_PARTB1);
}

void sort_shake(int s, int n, int k, int q) {
	sortSmaller(s, n, k, q, REGISTER_A, REGISTER_B);
	append_left(REGISTER_B, REGISTER_B, 2*k);
	sortSmaller(s, n, k, q, REGISTER_B, REGISTER_A);
	append_right(REGISTER_B, REGISTER_B, 2*k);
}

void construct_instructions(int s, int n, int k, int q) {
	
	if (s == TASK_SORT) {
		sortPrepare(s, n, k, q);
		// append_print(REGISTER_IO);
		// append_print(REGISTER_A);
		// append_print(REGISTER_B);
		loop(a, n / 2){
			sort_shake(s, n, k, q);
			// append_print(REGISTER_A);
			// append_print(REGISTER_B);
		}
		if (n % 2 == 1) sortSmaller(s, n, k, q, REGISTER_A, REGISTER_B);
		append_right(REGISTER_A, REGISTER_A, k);
		append_or(REGISTER_IO, REGISTER_A, REGISTER_B);
	}
	else if (s == TASK_MIN) {
		sortPrepare(s, n, k, q);
		// append_print(REGISTER_IO);
		// append_print(REGISTER_A);
		// append_print(REGISTER_B);
		while (n > 1) {
			sortSmaller(s, n, k, q, REGISTER_A, REGISTER_B);
			n = (n + 1) / 2;
			append_right(REGISTER_B, REGISTER_A, (2*k) * (n/2) );
			// append_print(REGISTER_A);
			// append_print(REGISTER_B);
		}
		append_right(REGISTER_A, REGISTER_A, k);
		append_or(REGISTER_IO, REGISTER_A, REGISTER_B);
	}
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct

Subtask #2
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Wrong answer detected in grader

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 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 0 ms 204 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 1 ms 288 KB Output is correct

Subtask #6
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 2 ms 416 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct