#include #include #include #include using namespace std; enum Type { _3x3 = 0, _3x2, _3x1, _2x2, _2x1, _1x1, MAX }; enum Orientation { Vertical = 0, Horizontal }; Type get_type(pair p) { if (p.first == p.second && p.first == 3) { return _3x3; } if (p.first == p.second && p.first == 2) { return _2x2; } if (p.first == p.second && p.first == 1) { return _1x1; } if (p.first > p.second) return get_type({p.second, p.first}); assert(p.first < p.second); if (p.first == 1 && p.second == 2) { return _2x1; } if (p.first == 1 && p.second == 3) { return _3x1; } if (p.first == 2 && p.second == 3) { return _3x2; } assert(false); } // col, row pair type_to_size(Type t, Orientation o) { static const pair m[MAX] = { {3, 3}, {3, 2}, {3, 1}, {2, 2}, {2, 1}, {1, 1}, }; auto sizes = m[t]; if (o == Vertical) { swap(sizes.first, sizes.second); } return sizes; } void fill(vector> &board, int col, int row, Type type, Orientation orientation, vector> &pieces) { auto& indices = pieces[type]; assert(indices.size() > 0); auto size = type_to_size(type, orientation); for (int i = col; i < col + size.first; ++i) { for (int j = row; j < row + size.second; ++j) { assert(i < board.size()); assert(j < board[i].size()); assert(board[i][j] == 0); board[i][j] = indices.back(); } } indices.pop_back(); } int main() { int K, N; cin >> K >> N; vector> pieces(K); for (int i = 0; i < K; ++i) { cin >> pieces[i].first; } for (int i = 0; i < K; ++i) { cin >> pieces[i].second; } vector> per_type(MAX); for (int i = 0; i < K; ++i) { per_type[get_type(pieces[i])].push_back(i + 1); } vector> board(N, {0, 0, 0}); int col = 0; while (per_type[_3x3].size()) { fill(board, col, 0, _3x3, /*does not matter*/ Vertical, per_type); col += 3; } const int start_2x2s = col; while (per_type[_2x2].size()) { fill(board, col, 0, _2x2, /*does not matter*/ Vertical, per_type); col += 2; } int col_under = start_2x2s; // Fill under the 2x2s. while (per_type[_3x1].size() && col_under <= 1 + col - 3) { fill(board, col_under, 2, _3x1, Horizontal, per_type); col_under += 3; } while (per_type[_2x1].size() && col_under <= 1 + col - 2) { fill(board, col_under, 2, _2x1, Horizontal, per_type); col_under += 2; } while (per_type[_1x1].size() && col_under <= col - 1) { fill(board, col_under, 2, _1x1, Horizontal, per_type); col_under += 1; } if (col_under == col + 1) { // Fill the vertical space. if (per_type[_2x1].size()) { fill(board, col, 0, _2x1, Vertical, per_type); col += 1; } else { assert(per_type[_1x1].size() >= 2); for (int i = 0; i < 2; ++i) { fill(board, col, i, _1x1, Vertical, per_type); } col += 1; } } assert(col_under == col); // We now have a rectangle to fill starting at 'col' with remaining: // _3x2, // _3x1, // _2x1, // _1x1 while (per_type[_3x2].size()) { fill(board, col, 0, _3x2, Vertical, per_type); col += 2; } while (per_type[_3x1].size()) { fill(board, col, 0, _3x1, Vertical, per_type); col += 1; } // Only 1x1 and 2x2 remaining. num(1x1) = num(2x1) mod 3. assert((static_cast(per_type[_2x1].size()) - static_cast(per_type[_1x1].size())) % 3 == 0); while (per_type[_2x1].size() && per_type[_1x1].size()) { fill(board, col, 0, _2x1, Vertical, per_type); fill(board, col, 2, _1x1, Vertical, per_type); col += 1; } // Now only either 1x1s or 2x1s (and multiple of 3s). while (per_type[_2x1].size()) { for (int row = 0; row < 3; ++row) { fill(board, col, row, _2x1, Horizontal, per_type); } col += 2; } while (per_type[_1x1].size()) { for (int row = 0; row < 3; ++row) { fill(board, col, row, _1x1, Horizontal, per_type); } col += 1; } assert(col == N); for (int row = 0; row < 3; ++row) { for (int c = 0; c < N; ++c) { cout << board[c][row] << " "; } cout << endl; } }