QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#803250#9874. Matrix Constructionucup-team159#AC ✓58ms15084kbC++203.6kb2024-12-07 16:37:082024-12-07 16:37:08

Judging History

你现在查看的是最新测评结果

  • [2024-12-07 16:37:08]
  • 评测
  • 测评结果:AC
  • 用时:58ms
  • 内存:15084kb
  • [2024-12-07 16:37:08]
  • 提交

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