QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#803250 | #9874. Matrix Construction | ucup-team159# | AC ✓ | 58ms | 15084kb | C++20 | 3.6kb | 2024-12-07 16:37:08 | 2024-12-07 16:37:08 |
Judging History
answer
#line 1 "M.cpp"
// #pragma GCC target("avx2,avx512f,avx512vl,avx512bw,avx512dq,avx512cd,avx512vbmi,avx512vbmi2,avx512vpopcntdq,avx512bitalg,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("Ofast")
#line 2 "/home/sigma/comp/library/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rep1(i,n) for(int i=1;i<=int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define per1(i,n) for(int i=int(n);i>0;i--)
#define all(c) c.begin(),c.end()
#define si(x) int(x.size())
#define pb push_back
#define eb emplace_back
#define fs first
#define sc second
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
template<class T,class U> bool chmax(T& x, U y){
if(x<y){ x=y; return true; }
return false;
}
template<class T,class U> bool chmin(T& x, U y){
if(y<x){ x=y; return true; }
return false;
}
template<class T> void mkuni(V<T>& v){sort(all(v));v.erase(unique(all(v)),v.end());}
template<class T> int lwb(const V<T>& v, const T& a){return lower_bound(all(v),a) - v.begin();}
template<class T>
V<T> Vec(size_t a) {
return V<T>(a);
}
template<class T, class... Ts>
auto Vec(size_t a, Ts... ts) {
return V<decltype(Vec<T>(ts...))>(a, Vec<T>(ts...));
}
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
o<<"{";
for(const T& v:vc) o<<v<<",";
o<<"}";
return o;
}
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }
#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
void dmpr(ostream& os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
os<<t<<" ~ ";
dmpr(os,args...);
}
#define shows(...) cerr << "LINE" << __LINE__ << " : ";dmpr(cerr,##__VA_ARGS__)
#define dump(x) cerr << "LINE" << __LINE__ << " : " << #x << " = {"; \
for(auto v: x) cerr << v << ","; cerr << "}" << endl;
#else
#define show(x) void(0)
#define dump(x) void(0)
#define shows(...) void(0)
#endif
template<class D> D divFloor(D a, D b){
return a / b - (((a ^ b) < 0 && a % b != 0) ? 1 : 0);
}
template<class D> D divCeil(D a, D b) {
return a / b + (((a ^ b) > 0 && a % b != 0) ? 1 : 0);
}
#line 5 "M.cpp"
bool ok(VV<int> a){
int H = si(a), W = si(a[0]), N = H*W;
V<bool> used(N+N+2);
rep(i,H) rep(j,W){
if(i != H-1){
if(used[a[i][j] + a[i+1][j]]) return false;
used[a[i][j] + a[i+1][j]] = true;
}
if(j != W-1){
if(used[a[i][j] + a[i][j+1]]) return false;
used[a[i][j] + a[i][j+1]] = true;
}
}
return true;
}
void solve(int H, int W){
bool swapped = false;
if(H%2) swap(H,W), swapped = true;
VV<int> a(H,V<int>(W));
if(H%2 == 0 && W%2 == 0){
rep(i,H) rep(j,W) a[i][j] = i*W+j+1;
}else{
rep(i,H) rep(j,W) a[i][j] = i*W+j+1;
rep(i,H) if(i%2) rotate(a[i].begin(),a[i].begin()+1,a[i].end());
}
// if(!ok(a)){
// cerr << H << ' ' << W << endl;
// rep(i,H) rep(j,W) cerr << a[i][j] << " \n"[j==W-1];
// }
if(swapped){
VV<int> b(W,V<int>(H));
rep(i,H) rep(j,W) b[j][i] = a[i][j];
swap(H,W);
a = b;
}
cout << "YES\n";
rep(i,H) rep(j,W) cout << a[i][j] << " \n"[j==W-1];
}
int main(){
cin.tie(0);
ios::sync_with_stdio(false); //DON'T USE scanf/printf/puts !!
cout << fixed << setprecision(20);
// rep1(H,10) rep1(W,10) solve(H,W);
// cerr << "OK" << endl;
int T; cin >> T;
while(T--){
int H,W; cin >> H >> W;
solve(H,W);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3568kb
input:
2 1 1 2 3
output:
YES 1 YES 1 2 3 5 6 4
result:
ok All test cases passed. (2 test cases)
Test #2:
score: 0
Accepted
time: 2ms
memory: 3592kb
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 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 10 19 20 21 22 23 24 25 26 27 29 30 31 32 33 34 35 36 28 YES 1 13 23 35 45 57 67 79 89 101 111 123 2 14 24 36 46 58 68 80 90 102 112 124 3 15 25 37 47 59 69 81 91 103 113 125 4 16 26 38 48 60 70 82 92 104 114 126 5 17 27 39 49 61 71 83 93 105 115 127 6 1...
result:
ok All test cases passed. (361 test cases)
Test #3:
score: 0
Accepted
time: 3ms
memory: 3700kb
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 27 51 77 101 127 151 177 2 28 52 78 102 128 152 178 3 29 53 79 103 129 153 179 4 30 54 80 104 130 154 180 5 31 55 81 105 131 155 181 6 32 56 82 106 132 156 182 7 33 57 83 107 133 157 183 8 34 58 84 108 134 158 184 9 35 59 85 109 1...
result:
ok All test cases passed. (264 test cases)
Test #4:
score: 0
Accepted
time: 7ms
memory: 3712kb
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 33 63 95 125 157 187 219 249 281 311 343 373 405 435 467 497 529 559 591 621 653 683 715 745 777 807 839 869 901 931 963 993 1025 1055 1087 1117 1149 1179 1211 1241 1273 1303 1335 1365 1397 1427 1459 1489 1521 1551 1583 1613 1645 1675 1707 1737 2 34 64 96 126 158 188 220 250 282 312 344 374 40...
result:
ok All test cases passed. (113 test cases)
Test #5:
score: 0
Accepted
time: 6ms
memory: 3940kb
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 17 31 47 61 77 91 107 121 137 151 167 181 197 211 227 241 257 271 287 301 317 331 347 361 377 391 407 421 437 451 467 481 497 511 527 541 557 571 587 601 617 631 647 661 677 691 707 721 737 751 767 781 797 811 827 841 857 871 887 901 917 931 947 2 18 32 48 62 78 92 108 122 138 152 168 182 198 ...
result:
ok All test cases passed. (127 test cases)
Test #6:
score: 0
Accepted
time: 31ms
memory: 3712kb
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: 35ms
memory: 3672kb
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 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 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 36 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. (199 test cases)
Test #8:
score: 0
Accepted
time: 6ms
memory: 3768kb
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 95 187 281 2 96 188 282 3 97 189 283 4 98 190 284 5 99 191 285 6 100 192 286 7 101 193 287 8 102 194 288 9 103 195 289 10 104 196 290 11 105 197 291 12 106 198 292 13 107 199 293 14 108 200 294 15 109 201 295 16 110 202 296 17 111 203 297 18 112 204 298 19 113 205 299 20 114 206 300 21 115 207...
result:
ok All test cases passed. (100 test cases)
Test #9:
score: 0
Accepted
time: 9ms
memory: 3912kb
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: 15ms
memory: 5320kb
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: 4ms
memory: 4448kb
input:
1 513 194
output:
YES 1 515 1027 1541 2053 2567 3079 3593 4105 4619 5131 5645 6157 6671 7183 7697 8209 8723 9235 9749 10261 10775 11287 11801 12313 12827 13339 13853 14365 14879 15391 15905 16417 16931 17443 17957 18469 18983 19495 20009 20521 21035 21547 22061 22573 23087 23599 24113 24625 25139 25651 26165 26677 27...
result:
ok All test cases passed. (1 test case)
Test #12:
score: 0
Accepted
time: 11ms
memory: 7060kb
input:
1 923 363
output:
YES 1 925 1847 2771 3693 4617 5539 6463 7385 8309 9231 10155 11077 12001 12923 13847 14769 15693 16615 17539 18461 19385 20307 21231 22153 23077 23999 24923 25845 26769 27691 28615 29537 30461 31383 32307 33229 34153 35075 35999 36921 37845 38767 39691 40613 41537 42459 43383 44305 45229 46151 47075...
result:
ok All test cases passed. (1 test case)
Test #13:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
1 141 19
output:
YES 1 143 283 425 565 707 847 989 1129 1271 1411 1553 1693 1835 1975 2117 2257 2399 2539 2 144 284 426 566 708 848 990 1130 1272 1412 1554 1694 1836 1976 2118 2258 2400 2540 3 145 285 427 567 709 849 991 1131 1273 1413 1555 1695 1837 1977 2119 2259 2401 2541 4 146 286 428 568 710 850 992 1132 1274 1...
result:
ok All test cases passed. (1 test case)
Test #14:
score: 0
Accepted
time: 1ms
memory: 3968kb
input:
1 63 188
output:
YES 1 65 127 191 253 317 379 443 505 569 631 695 757 821 883 947 1009 1073 1135 1199 1261 1325 1387 1451 1513 1577 1639 1703 1765 1829 1891 1955 2017 2081 2143 2207 2269 2333 2395 2459 2521 2585 2647 2711 2773 2837 2899 2963 3025 3089 3151 3215 3277 3341 3403 3467 3529 3593 3655 3719 3781 3845 3907 ...
result:
ok All test cases passed. (1 test case)
Test #15:
score: 0
Accepted
time: 21ms
memory: 5312kb
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: 26ms
memory: 6376kb
input:
1 840 945
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 #17:
score: 0
Accepted
time: 36ms
memory: 15084kb
input:
1 997 991
output:
YES 1 999 1995 2993 3989 4987 5983 6981 7977 8975 9971 10969 11965 12963 13959 14957 15953 16951 17947 18945 19941 20939 21935 22933 23929 24927 25923 26921 27917 28915 29911 30909 31905 32903 33899 34897 35893 36891 37887 38885 39881 40879 41875 42873 43869 44867 45863 46861 47857 48855 49851 50849...
result:
ok All test cases passed. (1 test case)
Test #18:
score: 0
Accepted
time: 34ms
memory: 11052kb
input:
1 971 997
output:
YES 1 973 1943 2915 3885 4857 5827 6799 7769 8741 9711 10683 11653 12625 13595 14567 15537 16509 17479 18451 19421 20393 21363 22335 23305 24277 25247 26219 27189 28161 29131 30103 31073 32045 33015 33987 34957 35929 36899 37871 38841 39813 40783 41755 42725 43697 44667 45639 46609 47581 48551 49523...
result:
ok All test cases passed. (1 test case)
Test #19:
score: 0
Accepted
time: 36ms
memory: 13896kb
input:
1 991 919
output:
YES 1 993 1983 2975 3965 4957 5947 6939 7929 8921 9911 10903 11893 12885 13875 14867 15857 16849 17839 18831 19821 20813 21803 22795 23785 24777 25767 26759 27749 28741 29731 30723 31713 32705 33695 34687 35677 36669 37659 38651 39641 40633 41623 42615 43605 44597 45587 46579 47569 48561 49551 50543...
result:
ok All test cases passed. (1 test case)
Test #20:
score: 0
Accepted
time: 35ms
memory: 7100kb
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: 35ms
memory: 7160kb
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: 3696kb
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: 26ms
memory: 3648kb
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