| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 690253 | maks007 | Red-blue table (IZhO19_stones) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}