#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
#define range(i, n) for (int i = 0; i < (n); ++i)
#define ar array
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
typedef long long ll;
typedef long double ld;
using namespace std;
//using namespace __gnu_pbds;
const ll INF = 1e18 + 5;
const int INFi = 1e9;
const int maxN = 1e6 + 1500;
const int md2 = 998244353;
const int md = 1e9 + 7;
vector<vector<int>> sol1(int n, int m) {
vector<vector<int>> res(n, vector<int> (m, 1));
vector<int> cnt(n, (m - 1) / 2);
set<pair<int, int>> can;
range(i, n) if (cnt[i]) can.insert({cnt[i], i});
for(int j = m - 1; j >= 0; --j) {
int need = n - (n - 1) / 2;
while(need && !can.empty()) {
auto [a, b] = *can.rbegin();
can.erase({a, b});
cnt[b]--;
res[b][j] = 0;
a--;
need--;
if (a) can.insert({a, b});
}
if (need) break;
}
return res;
}
vector<vector<int>> sol2(int n, int m) {
vector<vector<int>> res(n, vector<int> (m, 0));
vector<int> cnt(m, (n - 1) / 2);
set<pair<int, int>> can;
range(i, m) if (cnt[i]) can.insert({cnt[i], i});
for(int j = n - 1; j >= 0; --j) {
int need = m - (m - 1) / 2;
while(need && !can.empty()) {
auto [a, b] = *can.rbegin();
can.erase({a, b});
cnt[b]--;
res[j][b] = 1;
a--;
need--;
if (a) can.insert({a, b});
}
if (need) break;
}
return res;
}
int cnt(vector<vector<int>> &res) {
int ans = 0;
range(i, res.size()) {
int w = 0;
range(j, res[i].size()) {
if (res[i][j]) w++;
}
if (w > (int)res[i].size() - w) ans++;
}
range(j, res[0].size()) {
int w = 0;
range(i, res.size()) {
if (res[i][j] == 0) w++;
}
if (w > (int)res.size() - w) ans++;
}
return ans;
}
void print(vector<vector<int>> &res) {
cout << cnt(res) << '\n';
range(i, (int)res.size()) {
range(j, (int)res[i].size()) {
if (res[i][j]) cout << "+";
else cout << "-";
}
cout << '\n';
}
}
void solve() {
int n, m; cin >> n >> m;
auto A = sol1(n, m);
auto B = sol2(n, m);
if (cnt(A) > cnt(B)) {
print(A);
} else {
print(B);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
// cout << setprecision(15) << fixed;
int tests = 1;
cin >> tests;
range(_, tests) {
solve();
}
return 0;
}
Compilation message
stones.cpp: In function 'int cnt(std::vector<std::vector<int> >&)':
stones.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define range(i, n) for (int i = 0; i < (n); ++i)
| ^
stones.cpp:66:5: note: in expansion of macro 'range'
66 | range(i, res.size()) {
| ^~~~~
stones.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define range(i, n) for (int i = 0; i < (n); ++i)
| ^
stones.cpp:68:9: note: in expansion of macro 'range'
68 | range(j, res[i].size()) {
| ^~~~~
stones.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define range(i, n) for (int i = 0; i < (n); ++i)
| ^
stones.cpp:73:5: note: in expansion of macro 'range'
73 | range(j, res[0].size()) {
| ^~~~~
stones.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define range(i, n) for (int i = 0; i < (n); ++i)
| ^
stones.cpp:75:9: note: in expansion of macro 'range'
75 | range(i, res.size()) {
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
0 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
0 ms |
364 KB |
Output is correct |
| 3 |
Correct |
3 ms |
364 KB |
Output is correct |
| 4 |
Correct |
8 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
169 ms |
1516 KB |
Output is correct |
| 2 |
Correct |
167 ms |
6612 KB |
Output is correct |
| 3 |
Correct |
164 ms |
7088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
165 ms |
1644 KB |
Output is correct |
| 2 |
Correct |
151 ms |
5356 KB |
Output is correct |
| 3 |
Correct |
137 ms |
3728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
0 ms |
364 KB |
Output is correct |
| 3 |
Correct |
3 ms |
364 KB |
Output is correct |
| 4 |
Correct |
8 ms |
492 KB |
Output is correct |
| 5 |
Correct |
169 ms |
1516 KB |
Output is correct |
| 6 |
Correct |
167 ms |
6612 KB |
Output is correct |
| 7 |
Correct |
164 ms |
7088 KB |
Output is correct |
| 8 |
Correct |
165 ms |
1644 KB |
Output is correct |
| 9 |
Correct |
151 ms |
5356 KB |
Output is correct |
| 10 |
Correct |
137 ms |
3728 KB |
Output is correct |
| 11 |
Correct |
32 ms |
620 KB |
Output is correct |
| 12 |
Correct |
142 ms |
4604 KB |
Output is correct |
| 13 |
Correct |
147 ms |
3692 KB |
Output is correct |
| 14 |
Correct |
108 ms |
2664 KB |
Output is correct |
| 15 |
Correct |
190 ms |
9324 KB |
Output is correct |
| 16 |
Correct |
170 ms |
7020 KB |
Output is correct |
| 17 |
Correct |
60 ms |
3308 KB |
Output is correct |
