#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 );
}
