Submission #1198788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198788		hyakup	Bit Shift Registers (IOI21_registers)	C++20	100 / 100	4 ms	1604 KiB

registers

#include "registers.h"
#include <bits/stdc++.h>
using namespace std;

const int maxb = 2000;
const int maxn = 100;
const int logn = 7;

class Registers{
private:
	vector<int> free;
	int cont = 0;

	int create(){ return ++cont; }

public:
	int get(){
		if( free.empty() ) return create();
		int x = free.back(); free.pop_back();
		return x;
	}

	void take_back( int id ){
		free.push_back(id);
	}
} reg;


void append_extract_even( int goal, int source, int k, int delta ){
	vector<bool> v(maxb);
	for( int i = 0; i < maxb; i += delta ){
		for( int j = i; j < i + k; j++ ) v[j] = true;
	}
	int aux = reg.get();
	append_store( aux, v );
	append_and( goal, source, aux );
	reg.take_back(aux);
}

void append_extract_odd( int goal, int source, int k, int delta ){
	append_right( goal, source, delta/2 );
	append_extract_even( goal, goal, k, delta );
}

void append_subtract( int goal, int a, int b ){
	append_not( goal, b );
	append_add( goal, goal, a );
}

void append_spread( int goal, int k ){
	int aux = reg.get();
	append_right( aux, goal, k );
	append_and( goal, aux, goal );
	append_or( goal, aux, goal );
	reg.take_back(aux);
}

void append_fill( int goal, int qtd, int k, int delta ){
	vector<bool> v(maxb);
	for( int i = 0; i < maxb; i += delta ) if( i/delta >= qtd ){
		for( int j = i; j < i + k; j++ ) v[j] = true;
	}
	int aux = reg.get();
	append_store( aux, v );
	append_or( goal, goal, aux );
	reg.take_back(aux);
}

void append_clear( int goal, int qtd, int k, int delta ){
	vector<bool> v(maxb, true);
	for( int i = 0; i < maxb; i += delta ) if( i/delta >= qtd ){
		for( int j = i; j < i + k; j++ ) v[j] = false;
	}
	int aux = reg.get();
	append_store( aux, v );
	append_and( goal, goal, aux );
	reg.take_back(aux);
}

void get_min( int n, int k ){

	int total = n;

	for( int i = 1; total > 1; i *= 2 ){
		int a = reg.get();
		int b = reg.get();
		append_extract_even( a, 0, k, 2*k*i );
		append_extract_odd( b, 0, k, 2*k*i );

		int qtda = (total + 1)/2;
		int qtdb = total/2;

		append_fill( a, qtda, k, 2*k*i );
		append_fill( b, qtdb, k, 2*k*i );

		int sub = reg.get();
		append_subtract( sub, a, b );
		append_spread( sub, k );


		append_and( 0, sub, a );

		append_not( sub, sub );
		append_and( sub, sub, b );

		append_or( 0, 0, sub );

		total = qtda;

		reg.take_back(a);
		reg.take_back(b);
		reg.take_back(sub);
	}
}

void sort( int n, int k ){
	int sorted = reg.get();
	for( int i = 0; i < n; i++ ){
		int qtda, qtdb;
		if( i%2 == 1 ){
			append_right( sorted, 0, k );
			qtda = n/2;
			qtdb = (n - 1)/2;
		}
		else{
			append_move( sorted, 0 );
			qtda = (n + 1)/2;
			qtdb = n/2;
		}

		int a = reg.get();
		int b = reg.get();

		append_extract_even( a, sorted, k, 2*k );
		append_extract_odd( b, sorted, k, 2*k );

		append_fill( a, qtda, k, 2*k );
		append_fill( b, qtdb, k, 2*k );


		int sub = reg.get();
		int maiores = reg.get();
		int aux = reg.get();
		append_subtract( sub, a, b );
		append_spread( sub, k );

		append_and( sorted, sub, a );
		append_and( maiores, sub, b );

		append_not( sub, sub );
		append_and( aux, sub, a );
		append_and( sub, sub, b );

		append_or( maiores, maiores, aux );
		append_or( sorted, sorted, sub );

		append_left( maiores, maiores, k );
		append_or( sorted, sorted, maiores );

		if( i%2 == 1 ){
			append_left( sorted, sorted, k );
			append_clear( 0, 1, k, k );
			append_or( 0, sorted, 0 );
		}
		else append_move( 0, sorted );

		reg.take_back(a);
		reg.take_back(b);
		reg.take_back(sub);
		reg.take_back(maiores);
		reg.take_back(aux);

	}
}

void construct_instructions( int s, int n, int k, int q ){
	if( s == 0 ) get_min( n, k );
	else sort( n, k );
}

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 25 / 25
• Subtask 5: 13 / 13
• Subtask 6: 29 / 29