time limit per test2 seconds memory limit per test256 megabytes You are given π2 cardsβ¦
- User
time limit per test2 seconds memory limit per test256 megabytes
You are given π2 cards with values from 0 to π2β1 . You are to arrange them in a π by π grid such that there is exactly one card in each cell.
The MEX (minimum excluded value) of a subgridβ is defined as the smallest non-negative integer that does not appear in the subgrid.
Your task is to arrange the cards such that the sum of MEX values over all (π(π+1)2)2 subgrids is maximized.
β A subgrid of a π by π grid is specified by four numbers π1,π1,π2,π2 satisfying 1β€π1β€π1β€π and 1β€π2β€π2β€π . The element in the π -th row and the π -th column of the grid is part of the subgrid if and only if π1β€πβ€π1 and π2β€πβ€π2 .
Input Each test contains multiple test cases. The first line contains the number of test cases π‘ (1β€π‘β€100 ). The description of the test cases follows.
The first line of each test case contains a single integer π (1β€πβ€500 ) β the side length of the grid.
It is guaranteed that the sum of π over all test cases does not exceed 1000 .
Output For each test case, output π lines, each containing π integers representing the elements of the grid.
If there are multiple answers, you can output any of them.
Example InputCopy 2 2 3 OutputCopy 0 1 2 3 8 4 5 6 0 1 7 2 3 Note In the first test case, one valid arrangement is:
0 1 2 3 There are 9 subgrids in total, and the 4 of them with non-zero MEX are shown below:
0 values:[0] β MEX: 1 0 1 values:[0,1] β MEX: 2 0 2 values:[0,2] β MEX: 1 0 1 2 3 values:[0,1,2,3] β MEX: 4 The sum of MEX over all subgrids would be 1+2+1+4=8 . It can be proven that no other arrangements have a larger sum of MEX values.
Assistant
#include <iostream> #include <vector> #include <numeric> #include <algorithm> int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); int t; std::cin >> t; while (t--) { int n; std::cin >> n; std::vector<std::vector<int>> grid(n, std::vector<int>(n)); if (n == 1) { grid[0][0] = 0; } else { // Fill the bottom-right 2x2 block with 0, 1, 2, 3 // These are cells (i,j) where i,j in [n-2, n-1] for (int i = 0; i < 2; ++i) { for (int j = 0; j < 2; ++j) { grid[n - 2 + i][n - 2 + j] = i * 2 + j; } } // Collect cells NOT in the bottom-right 2x2 block // These are cells (i,j) where i < n-2 or j < n-2 std::vector<std::pair<int, int>> remaining_cells; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (i < n - 2 || j < n - 2) { remaining_cells.push_back({i, j}); } } } // Sort these cells lexicographically (row-major) std::sort(remaining_cells.begin(), remaining_cells.end()); // Assign values 4 to n^2-1 to these cells // Special case: cell (0,0) gets n^2-1 int current_value = 4; for (const auto& cell : remaining_cells) { if (cell.first == 0 && cell.second == 0) { // Assign n^2-1 later } else { grid[cell.first][cell.second] = current_value++; } } // Assign n^2-1 to cell (0,0) if it was in the remaining_cells set // (0,0) is in remaining_cells if 0 < n-2, which is true for n >= 3 if (n > 2) { grid[0][0] = n * n - 1; } // If n=2, remaining_cells is empty, (0,0) is in the 2x2 block and gets 0. } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { std::cout << grid[i][j] << (j == n - 1 ? "" : " "); } std::cout << "\n"; } } return 0; }
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.