제출 #690254

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
690254		maks007	Red-blue table (IZhO19_stones)	C++14	0 / 100	122 ms	262144 KiB

stones

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 ++) {
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 10
• Subtask 3: 0 / 16
• Subtask 4: 0 / 11
• Subtask 5: 0 / 15
• Subtask 6: 0 / 31