블록 부품 맞추기

#define MAX 30000
#define QSIZE 10
using namespace std;

class Status
{
private:
	int num[4], ind, mod[4][4], high;
	int f(int x)
	{
		return 81*81*81*num[x] + 81*81*num[(x+1)&3] + 81*num[(x+2)&3] + num[(x+3)&3];
	}
public:
	Status(){}
	Status(int m[4][4])
	{	
		high = -1;
		for(int i=0;i<4;i++) for(int j=0;j<4;j++)
		{
			mod[i][j]=m[i][j];
			if(mod[i][j]>high) high=mod[i][j];
		}
		num[0] = 27*m[0][0]+9*m[0][1]+3*m[1][0]+m[1][1];
		num[1] = 27*m[0][3]+9*m[1][3]+3*m[0][2]+m[1][2];
		num[2] = 27*m[3][3]+9*m[3][2]+3*m[2][3]+m[2][2];
		num[3] = 27*m[3][0]+9*m[2][0]+3*m[3][1]+m[2][1];
		
		ind=0;
		for(int i=1;i<4;i++)
		{
			int find = f(ind), fi = f(i);
			if(find>fi) ind=i;
		}
	}
	int get(int x){ return num[(ind+x)&3]; }
	bool operator==(Status& x)
	{
		for(int i=0;i<4;i++)
		{
			if(get(i)!=x.get(i)) return false;
		}
		return true;
	}
	bool operator<(Status& x)
	{
		for(int i=0;i<4;i++)
		{
			if(get(i)!=x.get(i)) return get(i)<x.get(i);
		}
		return false;
	}

	int getHigh(){return high;}
	Status flipComplement()
	{
		int t[4][4];
		for(int i=0;i<4;i++) for(int j=0;j<4;j++) t[i][j] = high - mod[i][3-j];
		return Status(t);
	}
};
struct Block
{
	Status st;
	int base;
	Block(){}
	Block(int _d[4][4], int _b)
	{
		st = Status(_d);
		base = _b;
	}
	bool operator<(Block& x)
	{
		if(st==x.st)return base>x.base;
		return st<x.st;
	}
};
class Queue{
private:
	int data[QSIZE];
	int f,b,s;
public:
	Queue()
	{
		f=b=s=0;
	}
	void push(int x)
	{
		data[b]=x;
		++b;
		++s;
		if(b==QSIZE) b=0;
	}	
	void pop()
	{
		++f;
		--s;
		if(f==QSIZE) f=0;
	}
	int front(){return data[f];}
	int size(){return s;}
};

class Data
{
public:
	Status status;
	Queue q;
	Data(){}
	Data(Status& _st)
	{
		status=_st;
		q=Queue();
	}
};
void swap(Block& x,Block& y)
{
	Block t=x;
	x=y;
	y=t;
}

void quickSort(int l,int r, Block* b)
{
	if(l+1>=r)return;
	
	int pivot = l;
	int j=pivot;
	
	for(int i=l+1;i<r;i++)
	{
		if(!(b[i]<b[pivot])) continue;
		j++;
		swap(b[i], b[j]);
	}

	swap(b[l], b[j]);

	pivot=j;
	quickSort(l, pivot, b);
	quickSort(pivot+1,r, b);
}

int binary_search(int l, int r, Status& v, Data* d)
{
	while(l<r)
	{
		int mid = (l+r)>>1;
		if(d[mid].status==v)return mid;
		
		if(d[mid].status<v) l=mid+1;
		else r=mid;
	}
	return -1;
}

Block b[MAX];
Data d[MAX];

int normalize(int module[4][4])
{
    int base=module[0][0];
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            if(base>module[i][j])
                base = module[i][j];
    
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            module[i][j] -= base;
    
    return base;
}

int makeBlock(int module[][4][4]) {
	for(int i=0;i<MAX;i++)
	{
		int base = normalize(module[i]);
		b[i] = Block(module[i], base);
	}
	quickSort(0, MAX, b);

	int dnum=0;
	for(int i=0;i<MAX;i++)
	{
		d[dnum]=Data(b[i].st);
		d[dnum].q.push(b[i].base);
		while(b[i].st == b[i+1].st)
		{
			d[dnum].q.push(b[i+1].base);
			++i;
		}
		++dnum;
	}

	int ans=0;
	for(int i=0;i<dnum;i++)
	{	
		if(d[i].q.size()==0)continue;
		Status target = d[i].status.flipComplement();
		int ind = binary_search(0, dnum, target, d);
		if(ind==-1) continue;

		if(i==ind)
		{
			while(d[i].q.size()>1)
			{
				ans += d[i].q.front();
				d[i].q.pop();
				ans += d[i].q.front();
				d[i].q.pop();
				ans += d[i].status.getHigh();
			}
			continue;
		}
		while(d[i].q.size()>0 && d[ind].q.size()>0)
		{
			ans += d[i].q.front() + d[ind].q.front() + d[i].status.getHigh();
			d[i].q.pop();
			d[ind].q.pop();
		}
	}
	return ans;
}