oj.uz

답안 #437148

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
437148 2021-06-25T23:02:53 Z Popax21 레지스터 (IOI21_registers) C++17
100 / 100
 3 ms 588 KB 
#include <assert.h>
#include "registers.h"

#define NUM_BITS 2000

static inline int ulong(int n) {
	int l = 0;
	while((1 << l) < n) l++;
	return l;
}

void calc_min(int n, int k) {
	//Fill rest of inputs with 1s
	{
		std::vector<bool> r(NUM_BITS);
		for(int b = 0; b < NUM_BITS; b++) r[b] = (b >= n*k);
		append_store(1, r);
		append_or(0, 0, 1);
	}

	//Register plane algorithm
	for(int i = 0; i < ulong(n); i++) {
		//Split registers into two planes
		append_move(1, 0);
		append_right(1, 1, k << i);

		//Calculate comparsion-add operands
		append_xor(2, 0, 1);
		append_and(3, 2, 0);
		append_and(4, 2, 1);
		append_not(4, 4);

		//Mask operands
		std::vector<bool> m(NUM_BITS);
		for(int b = 0; b < NUM_BITS; b++) m[b] = (((b/k) % (1 << (i+1))) == 0);
		append_store(5, m);
		append_and(3, 3, 5);
		append_and(4, 4, 5);

		//Calculate comparison masks (0 if a is bigger)
		append_add(3, 3, 4);
		append_right(3, 3, k);
		append_and(3, 3, 5);

		append_add(3, 3, 5);
		append_and(3, 3, 5);

		//Update planes
		append_and(0, 0, 3);
		append_not(3, 3);
		append_and(1, 1, 3);
		append_or(0, 0, 1);
	}
}

void bitonic_sort(int n, int k, int l) {
	//Create flip mask
	//If a bit is one, that means the bit has to be smaller in b, else in a
	{
		std::vector<bool> fm(NUM_BITS);
		for(int b = 0; b < NUM_BITS; b++) fm[b] = (b / ((k+1) << (l+1))) % 2;
		append_store(95, fm);
		append_not(96, 95);
	}

	//Iterations of the sorting network
	for(int p = l; p >= 0; p--) {
		//Split registers into planes
		append_move(1, 0);
		append_right(1, 1, (k+1) << p);

		//Calculate comparsion-add operands
		append_xor(2, 0, 1);

		append_and(3, 2, 0);
		append_xor(3, 3, 95);

		append_and(4, 2, 1);
		append_xor(4, 4, 96);

		//Mask operands
		append_and(3, 3, 97);
		append_and(4, 4, 97);

		//Calculate comparison masks (0 if we should swap)
		append_add(3, 3, 4);
		append_and(3, 3, 98);
		append_right(3, 3, k);

		append_add(3, 3, 97);
		append_and(3, 3, 97);

		{
			std::vector<bool> m(NUM_BITS);
			for(int b = 0; b < NUM_BITS; b++) {
				m[b] = (b % (k+1)) < k && ((b / ((k+1) << p)) % 2) == 0;
			}
			append_store(4, m);
			append_and(3, 3, 4);
		}

		append_not(4, 3);

		//Swap part 1
		append_move(2, 0);

		append_and(0, 0, 4);
		append_and(1, 1, 3);
		append_or(0, 0, 1);

		//Update masks
		append_left(2, 2, (k+1) << p);
		append_left(3, 3, (k+1) << p);
		append_left(4, 4, (k+1) << p);

		{
			std::vector<bool> m(NUM_BITS);
			for(int b = 0; b < NUM_BITS; b++) m[b] = (b < ((k+1) << p));
			append_store(5, m);
			append_or(4, 4, 5);
		}

		//Swap part 2
		append_and(0, 0, 4);
		append_and(2, 2, 3);
		append_or(0, 0, 2);
	}
}

void sort_array(int n, int k) {
	//Create input mask
	{
		std::vector<bool> m(NUM_BITS);

		for(int b = 0; b < NUM_BITS; b++) m[b] = (b % (k+1)) < k;
		append_store(97, m);
		append_not(98, 97);

		for(int b = 0; b < NUM_BITS; b++) m[b] = b < k;
		append_store(99, m);
	}

	//Insert carry-catcher filler
	for(int i = 0; i < n; i++) {
		append_left(1, 1, k+1);

		append_move(2, 0);
		append_and(2, 2, 99);
		append_or(1, 1, 2);

		append_right(0, 0, k);
	}
	append_move(0, 1);

	//Bitonic sorting network
	for(int i = 0; i < ulong(n); i++) bitonic_sort(n, k, i);

	//Remove carry-catcher filler
	//The array has to be sorted backwards
	for(int i = 0; i < n; i++) {
		append_left(1, 1, k);

		append_move(2, 0);
		append_and(2, 2, 99);
		append_or(1, 1, 2);

		append_right(0, 0, k+1);
	}
	append_move(0, 1);
}

void construct_instructions(int s, int n, int k, int q) {
	if(s == 0) calc_min(n, k);
	else if(s == 1) sort_array(n, k);
	else assert(false);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
12.0 / 12.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

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 1 ms 204 KB Output is correct

Subtask #5
13.0 / 13.0

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

Subtask #6
29.0 / 29.0

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