Submission #690253

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
690253	2023-01-30T05:26:44 Z	maks007	Red-blue table (IZhO19_stones)	C++14	Compilation error	0 ms	0 KB

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

Compilation message

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:119:4: error: 'else' without a previous 'if'
  119 |   }else {
      |    ^~~~
stones.cpp:120:10: error: 'm' was not declared in this scope
  120 |    st dp[m][(1 << n)];
      |          ^
stones.cpp:120:19: error: 'n' was not declared in this scope
  120 |    st dp[m][(1 << n)];
      |                   ^
stones.cpp:124:6: error: 'dp' was not declared in this scope
  124 |      dp[i][j].str = 0;
      |      ^~
stones.cpp:126:6: error: 'path' was not declared in this scope
  126 |      path[i][j] = {-1,-1};
      |      ^~~~
stones.cpp:139:15: error: 'dp' was not declared in this scope
  139 |        if(get(dp[i][mask], 1) <= get(merge(dp[i][mask], dp[i-1][mask2], v, 1), 1)) {
      |               ^~
stones.cpp:141:9: error: 'path' was not declared in this scope
  141 |         path[i][mask] = {i-1,mask2};
      |         ^~~~
stones.cpp:146:24: error: 'dp' was not declared in this scope
  146 |        if(v[j] == '+') dp[i][mask].col[j] ++;
      |                        ^~
stones.cpp:147:13: error: 'dp' was not declared in this scope
  147 |        else dp[i][mask].col[j]--;
      |             ^~
stones.cpp:149:75: error: 'dp' was not declared in this scope
  149 |       if(count(v.begin(), v.end(), '+') < count(v.begin(), v.end(), '-')) dp[i][mask].str = 1;
      |                                                                           ^~
stones.cpp:150:7: error: 'path' was not declared in this scope
  150 |       path[i][mask]={-1,-1};
      |       ^~~~
stones.cpp:157:15: error: 'dp' was not declared in this scope
  157 |     int cnt = dp[m-1][i].str;
      |               ^~
stones.cpp:163:18: error: no match for 'operator=' (operand types are 'std::pair<long long int, long long int>' and '<brace-enclosed initializer list>')
  163 |      add = {m-1,i};
      |                  ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from stones.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:390:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type) [with _T1 = long long int; _T2 = long long int; typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type = const std::pair<long long int, long long int>&]'
  390 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:393:41: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, const std::pair<long long int, long long int>&, const std::__nonesuch&>::type' {aka 'const std::pair<long long int, long long int>&'}
  390 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~    
  391 |   __and_<is_copy_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~        
  392 |          is_copy_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  393 |   const pair&, const __nonesuch&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:401:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type) [with _T1 = long long int; _T2 = long long int; typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type = std::pair<long long int, long long int>&&]'
  401 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:404:31: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, std::pair<long long int, long long int>&&, std::__nonesuch&&>::type' {aka 'std::pair<long long int, long long int>&&'}
  401 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~
  402 |   __and_<is_move_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  403 |          is_move_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  404 |   pair&&, __nonesuch&&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, const _U1&>, std::is_assignable<_T2&, const _U2&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(const std::pair<_U1, _U2>&) [with _U1 = _U1; _U2 = _U2; _T1 = long long int; _T2 = long long int]'
  418 |  operator=(const pair<_U1, _U2>& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note:   template argument deduction/substitution failed:
stones.cpp:163:18: note:   couldn't deduce template parameter '_U1'
  163 |      add = {m-1,i};
      |                  ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from stones.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:430:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, _U1&&>, std::is_assignable<_T2&, _U2&&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(std::pair<_U1, _U2>&&) [with _U1 = _U1; _U2 = _U2; _T1 = long long int; _T2 = long long int]'
  430 |  operator=(pair<_U1, _U2>&& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:430:2: note:   template argument deduction/substitution failed:
stones.cpp:163:18: note:   couldn't deduce template parameter '_U1'
  163 |      add = {m-1,i};
      |                  ^
stones.cpp:170:11: error: 'path' was not declared in this scope
  170 |     add = path[add.first][add.second];
      |           ^~~~
stones.cpp:178:26: error: 'a' was not declared in this scope
  178 |      if(v[i] & (1 << j)) a[J][i] = '+';
      |                          ^
stones.cpp:179:11: error: 'a' was not declared in this scope
  179 |      else a[J][i] = '-';
      |           ^
stones.cpp:184:41: error: 'a' was not declared in this scope
  184 |     for(int j = 0; j < m; j ++) cout << a[i][j];
      |                                         ^
stones.cpp: At global scope:
stones.cpp:189:2: error: expected unqualified-id before 'return'
  189 |  return 0;
      |  ^~~~~~
stones.cpp:190:1: error: expected declaration before '}' token
  190 | }
      | ^