#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) {
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 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 <= 5) {
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 {
//
// }
}
return 0;
}
Compilation message
stones.cpp: In function 'st merge(st, st, std::vector<char>)':
stones.cpp:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for(int i = 0; i < v.size(); i ++) {
| ~~^~~~~~~~~~
stones.cpp: In function 'int main()':
stones.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int j = 0; j < dp[n-1][i].col.size(); j ++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~
stones.cpp:95:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(int i = 0; i < v.size(); i ++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2050 ms |
5844 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
212 KB |
Output is correct |
| 3 |
Execution timed out |
2050 ms |
5844 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
110 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
106 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 |
Correct |
2 ms |
212 KB |
Output is correct |
| 3 |
Execution timed out |
2050 ms |
5844 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
