#include<bits/stdc++.h>
#define el '\n'
using namespace std ;
int dx[4] = {1 , 0 , -1 , 0};
int dy[4] = {0 , -1 , 0 , 1};
int n , m;
namespace sub_trau{
bool valid_input(){
return n <= 4 && m <= 4;
}
int x[50][50] , ans = 0 , cnt = 0;
vector<vector<int>> out;
void backtrack(int i , int j , int c){
x[i][j] = c;
cnt++;
for ( int dir = 0 ; dir < 4 ; dir++ ){
int new_i = i + dx[dir];
int new_j = j + dy[dir];
if (new_i <= n && new_j <= m && new_i >= 1 && new_j >= 1 && x[new_i][new_j] == -1){
backtrack(new_i , new_j , 1);
backtrack(new_i , new_j , 0);
}
}
if (cnt == n * m){
int col = 0 , row = 0;
for ( int u = 1 ; u <= n ; u++ ){
int red = 0 , blue = 0;
for ( int v = 1 ; v <= m ; v++ ){
if (x[u][v]) red++;
else blue++;
}
if (red > blue) row++;
}
for ( int v = 1 ; v <= m ; v++ ){
int red = 0 , blue = 0;
for ( int u = 1 ; u <= n ; u++ ){
if (x[u][v]) red++;
else blue++;
}
if (blue > red) col++;
}
if (col + row > ans){
ans = col + row;
out.clear();
for ( int u = 1 ; u <= n ; u++ ){
vector<int> cur;
for ( int v = 1 ; v <= m ; v++ ) cur.push_back(x[u][v]);
out.push_back(cur);
}
}
}
x[i][j] = -1;
cnt--;
}
void solve(){
memset(x , -1 , sizeof(x));
cnt = 0;
ans = 0;
out.clear();
backtrack(1 , 1 , 0);
backtrack(1 , 1 , 1);
cout << ans << el;
for ( auto x : out ){
for ( auto lmao : x ) cout << (lmao ? '+' : '-');
cout << el;
}
}
}
namespace sub_test{
const int N = 1e3 + 5;
char a[N][N];
int pos = 1 , parity = 1;
vector<int> up;
deque<pair<int , int>> fix;
vector<pair<int , int>> need_fix;
void init(){
pos = 1 , parity = 1;
up.clear();
fix.clear();
need_fix.clear();
}
void solve(){
init();
if (n < m){
int need = n / 2 + 1;
for ( int i = 1 ; i <= need ; i++ ){
for ( int j = 1 ; j <= m ; j++ ){
a[i][j] = '-';
}
}
for ( int i = need + 1 ; i <= n ; i++ ){
for ( int j = 1 ; j <= m ; j++ ) a[i][j] = '+';
}
for ( int i = need + 1 ; i <= n ; i++ ){
if (parity & 1){
for ( int j = 1 ; j <= m / 2 + 1 ; j++ ) swap(a[i][j] , a[pos][j]);
}
else {
for ( int j = m ; j > m - (m / 2 + 1) ; j-- ) swap(a[i][j] , a[pos][j]);
}
parity++;
pos++;
}
for ( int i = need + 1 ; i <= n ; i += 2 ){
if (i + 1 > n) break;
for ( int j = 1 ; j <= m / 2 + 1 ; j++ ) swap(a[i][j] , a[i + 1][j]);
}
for ( int i = need + 1 ; i <= n ; i++ ){
for ( int j = 1 ; j <= m ; j++ ){
if (a[i][j] == '+'){
up.push_back(i);
break;
}
}
}
for ( int i = 1 ; i <= n ; i++ ){
bool check = true;
for ( int j = 1 ; j <= m ; j++ ){
if (a[i][j] == '+'){
check = false;
break;
}
}
if (check && up.size()){
if (up.back() <= i) break;
for ( int j = 1 ; j <= m ; j++ ) swap(a[i][j] , a[up.back()][j]);
up.pop_back();
}
}
for ( int i = 1 ; i <= n ; i++ ){
int cnt = 0;
for ( int j = 1 ; j <= m ; j++ ) cnt += a[i][j] == '+';
if (cnt > m / 2 + 1) fix.push_back(make_pair(cnt , i));
else if (cnt < m / 2 + 1) need_fix.push_back(make_pair(cnt , i));
}
sort(need_fix.begin() , need_fix.end() , greater<pair<int , int>>());
for ( int i = 0 ; i < need_fix.size() ; i++ ){
if (fix.empty()) break;
int remain = m / 2 + 1 - need_fix[i].first;
while (!fix.empty()){
if (!remain) break;
while (fix.size() && fix.front().first == m / 2 + 1){
fix.pop_front();
}
pair<int , int> top = fix.front();
for ( int j = 1 ; j <= m ; j++ ){
if (!remain || top.first == m / 2 + 1) break;
if (a[need_fix[i].second][j] == '-' && a[top.second][j] == '+'){
swap(a[need_fix[i].second][j] , a[top.second][j]);
remain--;
top.first--;
}
}
fix.pop_front();
fix.push_back(top);
}
}
int row = 0 , col = 0;
for ( int u = 1 ; u <= n ; u++ ){
int red = 0 , blue = 0;
for ( int v = 1 ; v <= m ; v++ ){
if (a[u][v] == '+') red++;
else blue++;
}
if (red > blue) row++;
}
for ( int v = 1 ; v <= m ; v++ ){
int red = 0 , blue = 0;
for ( int u = 1 ; u <= n ; u++ ){
if (a[u][v] == '+') red++;
else blue++;
}
if (blue > red) col++;
}
cout << row + col << el;
for ( int i = 1 ; i <= n ; i++ ){
for ( int j = 1 ; j <= m ; j++ ) cout << a[i][j];
cout << el;
}
}
else {
int need = m / 2 + 1;
for ( int i = 1 ; i <= n ; i++ ){
for ( int j = 1 ; j <= need ; j++ ){
a[i][j] = '+';
}
}
for ( int i = 1 ; i <= n ; i++ ){
for ( int j = need + 1 ; j <= m ; j++ ) a[i][j] = '-';
}
for ( int j = need + 1 ; j <= m ; j++ ){
if (parity & 1){
for ( int i = 1 ; i <= n / 2 + 1 ; i++ ){
swap(a[i][j] , a[i][pos]);
}
}
else {
for ( int i = n ; i > n - (n / 2 + 1) ; i-- ) swap(a[i][j] , a[i][pos]);
}
parity++;
pos++;
}
for ( int j = need + 1 ; j <= m ; j += 2 ){
if (j + 1 > m) break;
for ( int i = 1 ; i <= n / 2 + 1 ; i++ ) swap(a[i][j] , a[i][j + 1]);
}
for ( int j = need + 1 ; j <= m ; j++ ){
for ( int i = 1 ; i <= n ; i++ ){
if (a[i][j] == '-'){
up.push_back(j);
break;
}
}
}
for ( int j = 1 ; j <= m ; j++ ){
bool check = true;
for ( int i = 1 ; i <= n ; i++ ){
if (a[i][j] == '-'){
check = false;
break;
}
}
if (check && up.size()){
if (up.back() <= j) break;
for ( int i = 1 ; i <= n ; i++ ) swap(a[i][j] , a[i][up.back()]);
up.pop_back();
}
}
for ( int j = 1 ; j <= m ; j++ ){
int cnt = 0;
for ( int i = 1 ; i <= n ; i++ ) cnt += a[i][j] == '-';
if (cnt > n / 2 + 1) fix.push_back(make_pair(cnt , j));
else if (cnt < n / 2 + 1) need_fix.push_back(make_pair(cnt , j));
}
sort(need_fix.begin() , need_fix.end() , greater<pair<int , int>>());
for ( int i = 0 ; i < need_fix.size() ; i++ ){
if (fix.empty()) break;
int remain = n / 2 + 1 - need_fix[i].first;
while (!fix.empty()){
if (!remain) break;
while (fix.size() && fix.front().first == n / 2 + 1){
fix.pop_front();
}
pair<int , int> top = fix.front();
for ( int j = 1 ; j <= n ; j++ ){
if (!remain || top.first == n / 2 + 1) break;
if (a[j][need_fix[i].second] == '+' && a[j][top.second] == '-'){
swap(a[j][need_fix[i].second] , a[j][top.second]);
remain--;
top.first--;
}
}
fix.pop_front();
fix.push_back(top);
}
}
int row = 0 , col = 0;
for ( int u = 1 ; u <= n ; u++ ){
int red = 0 , blue = 0;
for ( int v = 1 ; v <= m ; v++ ){
if (a[u][v] == '+') red++;
else blue++;
}
if (red > blue) row++;
}
for ( int v = 1 ; v <= m ; v++ ){
int red = 0 , blue = 0;
for ( int u = 1 ; u <= n ; u++ ){
if (a[u][v] == '+') red++;
else blue++;
}
if (blue > red) col++;
}
cout << row + col << el;
for ( int i = 1 ; i <= n ; i++ ){
for ( int j = 1 ; j <= m ; j++ ) cout << a[i][j];
cout << el;
}
}
}
}
signed main (){
// freopen("redblue.inp" , "r" , stdin);
// freopen("redblue.out" , "w" , stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--){
cin >> n >> m;
if (sub_trau::valid_input()){
sub_trau::solve();
continue;
// return 0;
}
sub_test::solve();
}
}
Compilation message
stones.cpp: In function 'void sub_test::solve()':
stones.cpp:147:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | for ( int i = 0 ; i < need_fix.size() ; i++ ){
| ~~^~~~~~~~~~~~~~~~~
stones.cpp:246:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
246 | for ( int i = 0 ; i < need_fix.size() ; i++ ){
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
537 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
537 ms |
604 KB |
Output is correct |
| 3 |
Correct |
20 ms |
344 KB |
Output is correct |
| 4 |
Runtime error |
1061 ms |
508 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
860 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
537 ms |
604 KB |
Output is correct |
| 3 |
Correct |
20 ms |
344 KB |
Output is correct |
| 4 |
Runtime error |
1061 ms |
508 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
