#include "bits/stdc++.h"
using namespace std;
#define int long long
struct st{
int str;
vector <int> col;
};
st merge(st a, st b, vector <char> v, int flag = 0) {
if(flag) {
a.str = b.str;
if(count(v.begin(), v.end(), '+') < count(v.begin(), v.end(), '-')) a.str ++;
a.col = b.col;
for(int i = 0; i < v.size(); i ++) {
if(v[i] == '+') a.col[i] ++;
else a.col[i] --;
}
return a;
}
a.str = b.str;
if(count(v.begin(), v.end(), '+') > count(v.begin(), v.end(), '-')) a.str ++;
a.col = b.col;
for(int i = 0; i < v.size(); i ++) {
if(v[i] == '+') a.col[i] ++;
else a.col[i] --;
}
return a;
}
int get(st val, int flag = 0) {
if(flag) {
int cnt = val.str;
for(auto i : val.col) {
cnt += (i > 0);
}
return cnt;
}
int cnt = val.str;
for(auto i : val.col) {
cnt += (i < 0);
}
return cnt;
}
signed main () {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T;
cin >> T;
while(T --) {
int n, m;
cin >> n >> m;
if(m <= n) {
st dp[n][(1 << m)];
pair <int,int> path[n][(1 << m)];
for(int i = 0; i < n; i ++) {
for(int j = 0; j < (1 << m); j ++) {
dp[i][j].str = 0;
dp[i][j].col.resize(m,0);
path[i][j] = {-1,-1};
}
}
for(int i = 0; i < n; i ++) {
for(int mask = 0; mask < (1 << m); mask ++) {
vector <char> v;
for(int j = 0; j < m; j ++) {
if(mask & (1 << j)) v.push_back('+');
else v.push_back('-');
}
reverse(v.begin(), v.end());
if(i) {
for(int mask2 = 0; mask2 < (1 << m); mask2 ++) {
if(get(dp[i][mask]) <= get(merge(dp[i][mask], dp[i-1][mask2], v)) ) {
dp[i][mask]=merge(dp[i][mask], dp[i-1][mask2], v);
path[i][mask] = {i-1,mask2};
}
}
}else {
for(int j = 0; j < m; j ++) {
if(v[j] == '+') dp[i][mask].col[j] ++;
else dp[i][mask].col[j]--;
}
if(count(v.begin(), v.end(), '+') > count(v.begin(), v.end(), '-')) dp[i][mask].str = 1;
path[i][mask]={-1,-1};
}
}
}
int ans = 0;
pair <int,int> add;
for(int i= 0; i < (1 << m); i++) {
int cnt = dp[n-1][i].str;
for(int j = 0; j < dp[n-1][i].col.size(); j ++) {
if(dp[n-1][i].col[j] < 0) cnt ++;
}
if(cnt >= ans) {
ans = cnt;
add = {n-1,i};
}
}
cout << ans << "\n";
vector <int> v;
v.push_back(add.second);
while(add.first != -1) {
add = path[add.first][add.second];
if(add.first == -1) break;
v.push_back(add.second);
}
reverse(v.begin(), v.end());
for(int i = 0; i < v.size(); i ++) {
for(int j = m-1; j >=0; j --) {
if(v[i] & (1 << j)) cout << '+';
else cout << '-';
}
cout << "\n";
}
}else {
st dp[m][(1 << n)];
pair <int,int> path[m][(1 << n)];
for(int i = 0; i < m; i ++) {
for(int j = 0; j < (1 << n); j ++) {
dp[i][j].str = 0;
dp[i][j].col.resize(m,0);
path[i][j] = {-1,-1};
}
}
for(int i = 0; i < m; i ++) {
for(int mask = 0; mask < (1 << n); mask ++) {
vector <char> v;
for(int j = 0; j < n; j ++) {
if(mask & (1 << j)) v.push_back('+');
else v.push_back('-');
}
reverse(v.begin(), v.end());
if(i) {
for(int mask2 = 0; mask2 < (1 << n); mask2 ++) {
if(get(dp[i][mask], 1) <= get(merge(dp[i][mask], dp[i-1][mask2], v, 1), 1)) {
dp[i][mask]=merge(dp[i][mask], dp[i-1][mask2], v, 1);
path[i][mask] = {i-1,mask2};
}
}
}else {
for(int j = 0; j < n; j ++) {
if(v[j] == '+') dp[i][mask].col[j] ++;
else dp[i][mask].col[j]--;
}
if(count(v.begin(), v.end(), '+') < count(v.begin(), v.end(), '-')) dp[i][mask].str = 1;
path[i][mask]={-1,-1};
}
}
}
int ans = 0;
pair <int,int> add;
for(int i= 0; i < (1 << n); i++) {
int cnt = dp[m-1][i].str;
for(int j = 0; j < dp[m-1][i].col.size(); j ++) {
if(dp[m-1][i].col[j] > 0) cnt ++;
}
if(cnt >= ans) {
ans = cnt;
add = {m-1,i};
}
}
cout << ans << "\n";
vector <int> v;
v.push_back(add.second);
while(add.first != -1) {
add = path[add.first][add.second];
if(add.first == -1) break;
v.push_back(add.second);
}
char a[n][m];
for(int i = v.size()-1; i >= 0; i --) {
int J = 0;
for(int j = n-1; j >=0; j --) {
if(v[i] & (1 << j)) a[J][i] = '+';
else a[J][i] = '-';
J ++;
}
}
for(int i= 0; i < n; i ++) {
for(int j = 0; j < m; j ++) cout << a[i][j];
cout << "\n";
}
}
}
return 0;
}
Compilation message
stones.cpp: In function 'st merge(st, st, std::vector<char>, long long int)':
stones.cpp:17:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for(int i = 0; i < v.size(); i ++) {
| ~~^~~~~~~~~~
stones.cpp:26:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for(int i = 0; i < v.size(); i ++) {
| ~~^~~~~~~~~~
stones.cpp: In function 'int main()':
stones.cpp:95:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(int j = 0; j < dp[n-1][i].col.size(); j ++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~
stones.cpp:112:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for(int i = 0; i < v.size(); i ++) {
| ~~^~~~~~~~~~
stones.cpp:158:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
158 | for(int j = 0; j < dp[m-1][i].col.size(); j ++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Wrong answer in test 2 4: 3 < 4 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
81 ms |
460 KB |
Wrong answer in test 3 45: 35 < 46 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Wrong answer in test 2 4: 3 < 4 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
108 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
122 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Wrong answer in test 2 4: 3 < 4 |
| 3 |
Halted |
0 ms |
0 KB |
- |
