QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#803873 | #9874. Matrix Construction | ucup-team3734# | AC ✓ | 138ms | 92524kb | C++23 | 2.9kb | 2024-12-07 19:16:49 | 2024-12-07 19:16:50 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
#define all(x) (x).begin(), (x).end()
vector<vector<int>> solve(int n, int m) {
vector<vector<int>> ans(n, vector<int>(m));
// Conditions from the original code:
// 1) If n == 1 or m == 1 or m is even, fill in simple row-major order
if (n == 1 || m == 1 || m % 2 == 0) {
int cur = 1;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
ans[i][j] = cur++;
return ans;
}
// 2) If n is even and m is odd, fill in column-major order
if (n % 2 == 0) {
int cur = 1;
for (int j = 0; j < m; ++j)
for (int i = 0; i < n; ++i)
ans[i][j] = cur++;
return ans;
}
// 3) If both n and m are odd:
// Use the cyclic shift approach described.
{
// Fill in row-major order
int cur = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
ans[i][j] = cur++;
}
}
// For every even row (1-based index), cyclically shift by one position
// i.e., for i = 1, 3, ... (0-based means i = 1, 3,... for the second, fourth row, etc.)
for (int i = 1; i < n; i += 2) {
// Shift ans[i] by one to the left
int first_val = ans[i][0];
for (int j = 0; j < m - 1; ++j) {
ans[i][j] = ans[i][j + 1];
}
ans[i][m - 1] = first_val;
}
return ans;
}
}
bool check_unique_adj_sums(const vector<vector<int>> &ans) {
int n = (int)ans.size();
int m = (int)ans[0].size();
unordered_set<int> seen;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
// Check right neighbor
if (j + 1 < m) {
int sum_right = ans[i][j] + ans[i][j + 1];
if (seen.find(sum_right) != seen.end()) return false;
seen.insert(sum_right);
}
// Check down neighbor
if (i + 1 < n) {
int sum_down = ans[i][j] + ans[i + 1][j];
if (seen.find(sum_down) != seen.end()) return false;
seen.insert(sum_down);
}
}
}
return true;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
auto ans = solve(n, m);
bool unique = check_unique_adj_sums(ans);
cout << (unique ? "yes\n" : "no\n");
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j)
cout << ans[i][j] << (j + 1 == m ? '\n' : ' ');
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3836kb
input:
2 1 1 2 3
output:
yes 1 yes 1 3 5 2 4 6
result:
ok All test cases passed. (2 test cases)
Test #2:
score: 0
Accepted
time: 5ms
memory: 3904kb
input:
361 4 9 11 12 16 14 3 7 17 13 1 19 12 3 15 19 11 3 8 18 13 10 8 13 9 18 14 11 7 13 6 16 12 13 1 6 11 15 18 19 5 6 17 19 2 3 17 11 16 19 6 14 5 9 7 2 5 11 15 16 3 15 7 11 16 2 19 15 5 19 2 17 13 12 3 5 19 14 6 3 18 2 16 4 6 8 10 9 17 4 5 16 17 9 16 11 6 9 16 5 3 19 18 9 13 9 12 19 6 13 17 15 13 7 12 ...
output:
yes 1 5 9 13 17 21 25 29 33 2 6 10 14 18 22 26 30 34 3 7 11 15 19 23 27 31 35 4 8 12 16 20 24 28 32 36 yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 6...
result:
ok All test cases passed. (361 test cases)
Test #3:
score: 0
Accepted
time: 5ms
memory: 3664kb
input:
264 23 1 25 8 21 15 23 21 9 20 23 9 7 22 19 24 8 23 12 21 10 23 23 7 21 19 9 25 9 21 25 21 25 18 16 24 22 24 16 23 1 21 22 6 14 24 11 22 15 25 17 20 25 16 23 3 16 21 21 21 3 20 20 21 7 20 3 23 3 21 21 5 22 19 9 23 20 23 6 22 24 10 22 8 20 2 12 20 20 25 24 22 23 15 22 13 25 22 24 3 13 20 3 24 15 23 2...
output:
yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 8...
result:
ok All test cases passed. (264 test cases)
Test #4:
score: 0
Accepted
time: 14ms
memory: 4112kb
input:
113 31 57 57 1 57 25 29 57 57 54 36 57 26 57 2 57 57 48 14 57 57 6 57 53 38 57 15 57 57 43 3 57 57 38 18 57 23 57 57 35 57 56 1 57 57 3 57 50 20 57 9 57 57 34 42 57 16 57 57 4 56 57 57 7 57 20 57 11 34 57 53 57 7 57 49 57 19 57 32 57 57 19 57 42 57 8 57 10 5 57 21 57 37 57 57 40 22 57 57 2 13 57 33 ...
output:
yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102...
result:
ok All test cases passed. (113 test cases)
Test #5:
score: 0
Accepted
time: 31ms
memory: 3936kb
input:
127 15 64 64 2 33 64 64 31 64 11 64 41 64 49 7 64 64 48 64 18 64 53 64 26 61 64 10 64 64 24 20 64 37 64 64 34 64 32 64 4 64 46 64 47 64 42 11 64 64 6 48 64 64 12 64 7 64 45 64 50 6 64 64 22 64 1 64 61 19 64 64 17 60 64 22 64 64 9 64 62 64 57 26 64 64 33 54 64 28 64 2 64 32 64 29 64 35 64 36 64 64 51...
output:
yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
result:
ok All test cases passed. (127 test cases)
Test #6:
score: 0
Accepted
time: 104ms
memory: 4328kb
input:
195 44 98 98 92 98 20 50 98 98 31 98 75 98 68 37 98 5 98 41 98 34 98 98 46 98 91 98 90 98 22 98 11 9 98 98 58 98 52 39 98 18 98 19 98 98 87 98 10 66 98 11 98 36 98 85 98 88 98 84 98 98 21 64 98 98 37 20 98 98 6 98 67 1 98 47 98 38 98 29 98 98 86 23 98 56 98 98 59 45 98 63 98 60 98 98 79 93 98 24 98 ...
output:
yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
result:
ok All test cases passed. (195 test cases)
Test #7:
score: 0
Accepted
time: 116ms
memory: 4412kb
input:
199 100 35 100 85 77 100 100 36 75 100 100 42 100 28 89 100 54 100 97 100 22 100 100 50 86 100 100 22 63 100 17 100 32 100 58 100 74 100 9 100 100 29 100 97 100 77 20 100 100 62 56 100 100 41 1 100 100 8 50 100 60 100 15 100 100 74 100 75 100 67 100 49 81 100 100 63 100 89 100 7 70 100 100 93 100 59...
output:
yes 1 101 201 301 401 501 601 701 801 901 1001 1101 1201 1301 1401 1501 1601 1701 1801 1901 2001 2101 2201 2301 2401 2501 2601 2701 2801 2901 3001 3101 3201 3301 3401 2 102 202 302 402 502 602 702 802 902 1002 1102 1202 1302 1402 1502 1602 1702 1802 1902 2002 2102 2202 2302 2402 2502 2602 2702 2802 ...
result:
ok All test cases passed. (199 test cases)
Test #8:
score: 0
Accepted
time: 23ms
memory: 4044kb
input:
100 93 4 25 100 87 56 44 54 9 7 20 84 4 56 7 85 77 81 78 35 22 53 5 54 88 70 91 8 96 11 16 74 26 22 11 80 50 84 69 94 41 42 15 29 63 28 36 3 9 78 56 8 24 86 46 76 87 39 41 73 10 18 42 65 59 4 96 56 29 46 97 77 66 23 63 99 90 39 44 35 47 66 59 69 62 39 39 76 21 69 79 40 48 58 23 26 38 76 37 10 6 64 6...
output:
yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
result:
ok All test cases passed. (100 test cases)
Test #9:
score: 0
Accepted
time: 21ms
memory: 5740kb
input:
25 80 180 183 125 111 43 118 164 21 67 175 160 149 149 14 92 34 174 50 13 150 107 185 102 61 194 59 139 49 38 160 133 30 12 10 140 8 100 200 3 82 16 160 52 158 165 8 161 82 133
output:
yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
result:
ok All test cases passed. (25 test cases)
Test #10:
score: 0
Accepted
time: 60ms
memory: 46932kb
input:
1 590 834
output:
yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
result:
ok All test cases passed. (1 test case)
Test #11:
score: 0
Accepted
time: 15ms
memory: 13112kb
input:
1 513 194
output:
yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
result:
ok All test cases passed. (1 test case)
Test #12:
score: 0
Accepted
time: 43ms
memory: 30948kb
input:
1 923 363
output:
yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
result:
ok All test cases passed. (1 test case)
Test #13:
score: 0
Accepted
time: 1ms
memory: 4100kb
input:
1 141 19
output:
yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 20 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 58 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 97 98 99 100 101 102...
result:
ok All test cases passed. (1 test case)
Test #14:
score: 0
Accepted
time: 2ms
memory: 4644kb
input:
1 63 188
output:
yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
result:
ok All test cases passed. (1 test case)
Test #15:
score: 0
Accepted
time: 62ms
memory: 49496kb
input:
1 840 630
output:
yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
result:
ok All test cases passed. (1 test case)
Test #16:
score: 0
Accepted
time: 110ms
memory: 85872kb
input:
1 840 945
output:
yes 1 841 1681 2521 3361 4201 5041 5881 6721 7561 8401 9241 10081 10921 11761 12601 13441 14281 15121 15961 16801 17641 18481 19321 20161 21001 21841 22681 23521 24361 25201 26041 26881 27721 28561 29401 30241 31081 31921 32761 33601 34441 35281 36121 36961 37801 38641 39481 40321 41161 42001 42841 ...
result:
ok All test cases passed. (1 test case)
Test #17:
score: 0
Accepted
time: 112ms
memory: 91684kb
input:
1 997 991
output:
yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
result:
ok All test cases passed. (1 test case)
Test #18:
score: 0
Accepted
time: 117ms
memory: 90436kb
input:
1 971 997
output:
yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
result:
ok All test cases passed. (1 test case)
Test #19:
score: 0
Accepted
time: 105ms
memory: 86632kb
input:
1 991 919
output:
yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
result:
ok All test cases passed. (1 test case)
Test #20:
score: 0
Accepted
time: 104ms
memory: 92396kb
input:
1 996 1000
output:
yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
result:
ok All test cases passed. (1 test case)
Test #21:
score: 0
Accepted
time: 138ms
memory: 92524kb
input:
1 1000 1000
output:
yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
result:
ok All test cases passed. (1 test case)
Test #22:
score: 0
Accepted
time: 58ms
memory: 3656kb
input:
1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1 1000 1...
output:
yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
result:
ok All test cases passed. (1000 test cases)
Test #23:
score: 0
Accepted
time: 36ms
memory: 3936kb
input:
1000 1 1000 1 999 1 998 1 997 1 996 1 995 1 994 1 993 1 992 1 991 1 990 1 989 1 988 1 987 1 986 1 985 1 984 1 983 1 982 1 981 1 980 1 979 1 978 1 977 1 976 1 975 1 974 1 973 1 972 1 971 1 970 1 969 1 968 1 967 1 966 1 965 1 964 1 963 1 962 1 961 1 960 1 959 1 958 1 957 1 956 1 955 1 954 1 953 1 952 ...
output:
yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
result:
ok All test cases passed. (1000 test cases)
Extra Test:
score: 0
Extra Test Passed