template <class T>
class _vector {
public:
int _size;
int capacity;
T *arr;
_vector() {
_size = 0;
capacity = 32;
arr = new T[capacity];
}
_vector(int k) {
_size = k;
capacity = k;
arr = new T[capacity];
}
~_vector() {
delete[] arr;
}
void clear() {
delete[] arr;
_size = 0;
capacity = 32;
arr = new T[capacity];
}
void resize(int k) {
T *temp;
temp = new T[k];
for (int i = 0; i < _size; i++)
temp[i] = arr[i];
delete[] arr;
arr = temp;
_size = capacity = k;
}
int size() const {
return _size;
}
bool empty()const {
return _size == 0;
}
T back()const {
return arr[_size - 1];
}
T* begin() const {
return &arr[0];
}
T* end() const {
return &arr[0] + _size;
}
void push_back(T val) {
if (_size == capacity) {
resize(_size * 2);
_size /= 2;
}
arr[_size++] = val;
}
void pop_back() {
_size--;
}
T& operator [](int idx) {
return arr[idx];
}
T operator [](int idx)const {
return arr[idx];
}
};
//////////////////////////////////////////////////////////////
// sort stl
template <typename It>
void swap(It &a, It &b) {
It c(a); a = b; b = c;
}
template <typename It>
void sort(It begin, It end) {
if (begin == end)
return;
swap(*begin, *((end - begin) / 2 + begin));
It pi = begin;
It le = begin + 1;
It ri = end - 1;
while (le <= ri) {
while (le <= ri && !(*pi < *le))
le++;
while (le <= ri && !(*ri < *pi))
ri--;
if (le <= ri)
swap(*le, *ri);
}
swap(*pi, *ri);
sort(begin, ri);
sort(ri + 1, end);
}
template <typename A, typename B>
struct pair {
A first;
B second;
pair(A a, B b) :first(a), second(b) {}
pair() {}
bool operator < (const pair<int, int> &rhs)const {
if (rhs.first == first)return second < rhs.second;
return first < rhs.first;
}
};
///////////////////////////////////////////////////////////////
#define MAX 30000
int max(int a, int b) {
return a > b ? a : b;
}
int min(int a, int b) {
return a < b ? a : b;
}
int base[MAX], diff[MAX], sum[MAX], ss[MAX];
bool chk[MAX];
_vector<int> mp[MAX];
pair<int, int> vec[MAX];
int get_idx(int x) {
int it = MAX;
int le = 0, ri = MAX - 1, mid;
while (le <= ri) {
mid = (le + ri) / 2;
if (ss[mid] >= x) {
it = mid;
ri = mid - 1;
}
else le = mid + 1;
}
if (it == MAX || ss[it] != x)return -1;
return it;
}
void flip(int mat[4][4]) {
for (int i = 0; i < 4; i++) {
swap(mat[i][0], mat[i][3]);
swap(mat[i][1], mat[i][2]);
}
}
void rotate(int mat[4][4]) {
int temp[4][4];
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
temp[j][3 - i] = mat[i][j];
}
}
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
mat[i][j] = temp[i][j];
}
}
}
int makeBlock(int module[][4][4]) {
for (int i = 0; i < MAX; i++) mp[i].clear();
for (int i = 0; i < MAX; i++) {
chk[i] = false;
base[i] = 10;
for (int j = 0; j < 4; j++) {
for (int k = 0; k < 4; k++) {
base[i] = min(base[i], module[i][j][k]);
}
}
diff[i] = 0;
sum[i] = 0;
for (int j = 0; j < 4; j++) {
for (int k = 0; k < 4; k++) {
int now = module[i][j][k] - base[i];
sum[i] = sum[i] * 3 + now;
diff[i] = max(diff[i], module[i][j][k] - base[i]);
}
}
vec[i] = { base[i] + diff[i],i };
ss[i] = sum[i];
}
sort(vec, vec + MAX);
sort(ss, ss + MAX);
for (int i = 0; i < MAX; i++) {
int idx = vec[i].second;
mp[get_idx(sum[idx])].push_back(idx);
}
int ret = 0;
for (int i = MAX - 1; i >= 0; i--) {
int idx = vec[i].second;
if (chk[idx])continue;
mp[get_idx(sum[idx])].pop_back();
chk[idx] = true;
int temp[4][4];
for (int j = 0; j < 4; j++)for (int k = 0; k < 4; k++)temp[j][k] = module[idx][j][k];
flip(temp);
bool flag = false;
for (int j = 0; j < 4; j++) {
if (j)rotate(temp);
int tsum = 0;
for (int x = 0; x < 4; x++)for (int y = 0; y < 4; y++) {
int now = diff[idx] - (temp[x][y] - base[idx]);
tsum = tsum * 3 + now;
}
tsum = get_idx(tsum);
if (tsum == -1 || mp[tsum].empty())continue;
int it = mp[tsum].back();
chk[it] = true;
ret += base[idx] + base[it] + diff[it];
mp[tsum].pop_back();
flag = true;
break;
}
}
return ret;
}
댓글