#include using namespace std; #define ll long long using Clock = chrono::steady_clock; const int MAXN = 32; int backtracking_counter = 0; struct Point { int x, y; }; ll N, a, b, cVal, d, e, fVal; typedef vector> Board; Board bestBoard; vector> bestSol; int bestMoves = 0; Clock::time_point startTime = Clock::now(); struct Range { int rowStart, rowEnd, colStart, colEnd; }; vector block0 = { {0,0}, {-1,0}, {0,-1}, {-1,-1} }; vector block1 = { {0,0}, {-1,0}, {0,-1} }; vector block2 = { {0,0}, {-1,0}, {-2,0}, {0,-1} }; vector block3 = { {0,0}, {-1,0}, {-2,0}, {-3,0} }; vector block4 = { {0,0}, {0,-1}, {-1,-1}, {0,-2} }; vector> baseBlocks = { block0, block1, block2, block3, block4 }; struct MoveCandidate { double score; int i, j; }; Point rotatePoint(const Point &p, int rot) { int r = p.y, c = p.x; for (int i = 0; i < rot; i++){ int newR = c, newC = -r; r = newR; c = newC; } return {c, r}; } vector rotateBlock(const vector& block, int rot) { vector res; res.reserve(block.size()); for (const auto &p : block) res.push_back(rotatePoint(p, rot)); return res; } Range computeRangeExpanded(const vector& shape, int i, int j, int n) { int minRow = INT_MAX, maxRow = INT_MIN, minCol = INT_MAX, maxCol = INT_MIN; for (const auto &p : shape) { int r = i + p.y, c = j + p.x; minRow = min(minRow, r); maxRow = max(maxRow, r); minCol = min(minCol, c); maxCol = max(maxCol, c); } Range range; range.rowStart = max(0, minRow - 1); range.rowEnd = min(n, maxRow + 2); range.colStart = max(0, minCol - 1); range.colEnd = min(n, maxCol + 2); return range; } int countRow(const bitset &row, int n) { int cnt = 0; for (int j = 0; j < n; j++) { if (row.test(j)) cnt++; } return cnt; } void clearFullRowsCols(Board &board, const Range &range) { int n = board.size(); vector fullRow(n, false), fullCol(n, false); for (int r = range.rowStart; r < range.rowEnd; r++){ bool isFull = true; for (int c = 0; c < n; c++){ if (!board[r].test(c)) { isFull = false; break; } } if (isFull) fullRow[r] = true; } for (int c = range.colStart; c < range.colEnd; c++){ bool isFull = true; for (int r = 0; r < n; r++){ if (!board[r].test(c)) { isFull = false; break; } } if (isFull) fullCol[c] = true; } for (int r = 0; r < n; r++){ if (fullRow[r]) for (int c = 0; c < n; c++) board[r].reset(c); } for (int c = 0; c < n; c++){ if (fullCol[c]) for (int r = 0; r < n; r++) board[r].reset(c); } } Board makeBoard(int n) { return Board(n, bitset()); } void readInput(ll &N, ll &a, ll &b, ll &cVal, ll &d, ll &e, ll &fVal) { cin >> N >> a >> b >> cVal >> d >> e >> fVal; } void setupIO(){ ios::sync_with_stdio(false); cin.tie(nullptr); freopen("block.in", "r", stdin); freopen("block.out", "w", stdout); readInput(N, a, b, cVal, d, e, fVal); } tuple computeEmptyMetrics(const Board &board) { int n = board.size(), totalArea = 0, totalPerimeter = 0, numComponents = 0; bool visited[MAXN][MAXN] = {false}; int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1}; for (int r = 0; r < n; r++){ for (int c = 0; c < n; c++){ if (!board[r].test(c) && !visited[r][c]){ numComponents++; int area = 0, perimeter = 0; deque> dq; dq.push_back({r, c}); visited[r][c] = true; while(!dq.empty()){ auto cur = dq.front(); dq.pop_front(); area++; for (int k = 0; k < 4; k++){ int nr = cur.first + dr[k], nc = cur.second + dc[k]; if(nr < 0 || nr >= n || nc < 0 || nc >= n || board[nr].test(nc)) perimeter++; else if (!visited[nr][nc]){ visited[nr][nc] = true; dq.push_back({nr, nc}); } } } totalArea += area; totalPerimeter += perimeter; } } } return {totalArea, totalPerimeter, numComponents}; } Board applyShape(const Board &board, const vector &shape, int i, int j) { Board newBoard = board; int n = board.size(); for (const auto &p : shape) newBoard[i + p.y].set(j + p.x); Range range = computeRangeExpanded(shape, i, j, n); clearFullRowsCols(newBoard, range); return newBoard; } double computeHeuristic(const Board &board, const vector &shape, int i, int j) { Board newBoard = applyShape(board, shape, i, j); int emptyArea, emptyPerimeter, numRegions; tie(emptyArea, emptyPerimeter, numRegions) = computeEmptyMetrics(newBoard); const double wArea = 0.7, wPerimeter = 1.0, wComponents = 100.0; return - (wArea * emptyArea + wPerimeter * emptyPerimeter + wComponents * numRegions); } bool canPlaceShape(const Board &board, const vector &shape, int i, int j) { int n = board.size(); for (const auto &p : shape) { int rr = i + p.y, cc = j + p.x; if (rr < 0 || rr >= n || cc < 0 || cc >= n || board[rr].test(cc)) return false; } return true; } vector generateCandidates(const Board &board, const vector &shape) { int n = board.size(); vector candidates; for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++){ if (!canPlaceShape(board, shape, i, j)) continue; double score = computeHeuristic(board, shape, i, j); candidates.push_back({score, i, j}); } } return candidates; } vector> moves; void dfs(Board board, ll curC, ll curF) { double elapsed = chrono::duration_cast(Clock::now() - startTime).count() / 1000.0; if (elapsed >= 4.5) { if (moves.size() > bestMoves) { bestMoves = moves.size(); bestSol = moves; bestBoard = board; } return; } ll newC = (curC ^ a) + b, newF = (curF ^ d) + e; int blk = newC % 5, rot = newF % 4; vector shape = rotateBlock(baseBlocks[blk], rot); vector candidates = generateCandidates(board, shape); if (candidates.empty()){ if (moves.size() > bestMoves) { bestMoves = moves.size(); bestSol = moves; bestBoard = board; } backtracking_counter++; return; } sort(candidates.begin(), candidates.end(), [](const MoveCandidate &a, const MoveCandidate &b){ return a.score > b.score; }); if (candidates.size() > 3) candidates.resize(3); for (auto &cand : candidates){ moves.push_back({cand.i + 1, cand.j + 1}); Board nextBoard = applyShape(board, shape, cand.i, cand.j); dfs(nextBoard, newC, newF); moves.pop_back(); } } void solve(){ Board board = makeBoard(N); dfs(board, cVal, fVal); cout << bestSol.size() << "\n"; for (auto &p : bestSol) cout << p.first << " " << p.second << "\n"; } int main(){ setupIO(); solve(); return 0; }