oj.uz

Submission #690058

# Submission time Handle Problem Language Result Execution time Memory
690058 2023-01-30T04:07:41 Z iskhakkutbilim Red-blue table (IZhO19_stones) C++14
100 / 100
 165 ms 17088 KB 
#include <bits/stdc++.h>
using namespace std;

//#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()

struct print{
	int answer;
	vector< vector<int> > arr;	
};
print ANS;
int n, m, t;
int calc(vector<vector<int> > &a){
	int all = 0;
	for(int i = 0;i < n; i++){
		int blue = 0;
		for(int j = 0;j < m; j++){
			blue+= a[i][j];
		}
		if(blue >= m-(m / 2) and blue > m/2) all++;
	}
	for(int j = 0;j < m; j++){
		int red = 0;
		for(int i = 0;i < n; i++){
			red+= (a[i][j] == 0);
		}
		if(red >= n-(n / 2) and red > n/2) all++;
	}
	return all;
}


void subtask(){
	vector< vector<int> > a(n, vector<int>(m,0));
	set<pair<int, int> > st;
	vector< pair<int, int> > del;
	for(int i = 0;i < m; i++){
		st.insert({0, i});
	}
	int col = max(n / 2+1, n-(n / 2));
	int row = max(m/2+1, m - m/2);
	for(int i = 0;!st.empty() and i < n; i++){
		int cnt = row;
		for(pair<int, int> x : st){
			if(cnt == 0) break;
			cnt--;
			if(x.ff== n-col){
				st.clear();
				break;
			}
			a[i][x.ss] = 1;
			del.push_back(x);
		}
		for(pair<int, int> x : del){
			st.erase(x);
			st.insert({x.ff+1, x.ss});
		}
		del.clear();
	}
	int S = calc(a);
	if(S > ANS.answer){
		ANS = {S, a};
	}
}

void subtask2(){
	vector< vector<int> > a(n, vector<int>(m,1));
	set<pair<int, int> > st;
	vector< pair<int, int> > del;
	for(int i = 0;i < n; i++){
		st.insert({0, i});
	}
	int col = max(n / 2+1, n-(n / 2));
	int row = max(m/2+1, m - m/2);
	for(int j = 0;!st.empty() and j < m; j++){
		int cnt = col;
		for(pair<int, int> x : st){
			if(cnt == 0) break;
			cnt--;
			if(x.ff== m-row){
				st.clear();
				break;
			}
			a[x.ss][j] = 0;
			del.push_back(x);
		}
		for(pair<int, int> x : del){
			st.erase(x);
			st.insert({x.ff+1, x.ss});
		}
		del.clear();
	}
	int S = calc(a);
	if(S > ANS.answer){
		ANS = {S, a};
	}
}

void solve(){
	 cin >> n >> m;
	vector< vector<int> > a(n, vector<int>(m,0));
	ANS = {0, a};
	if(t <= 16 and max(n, m)<= 4){
		int answer = 0, s = 0, MASK=0;
		vector<pair<int,int>> cell(n*m);
		for(int i = 0;i < n; i++){
			for(int j = 0;j < m; j++){
				cell[s] = {i, j};
				s++;
			}
		}
		for(int mask = 0; mask < (1<<(n*m)); mask++){
			for(int i = 0;i < n*m; i++){
				if(mask & (1<<i)){
					a[cell[i].ff][cell[i].ss] = 1;
				}else{
					a[cell[i].ff][cell[i].ss] = 0;
				}
			}
			int S = calc(a);
			
			if(answer < S){
				answer = S;
				MASK = mask;
			}
		}
		for(int i = 0;i < n*m; i++){
			if(MASK & (1<<i)){
				a[cell[i].ff][cell[i].ss] = 1;
			}else{
				a[cell[i].ff][cell[i].ss] = 0;
			}
		}
		cout << answer << '\n';
		for(int i = 0;i < n; i++){
			for(int j = 0;j < m; j++){
				cout << (a[i][j] ? '+' : '-'); 
			}
			cout << '\n';
		}
		return;
	}
	subtask();
	subtask2();
	cout << ANS.answer << '\n';
	for(int i = 0;i < n; i++){
		for(int j = 0;j < m; j++){
			cout << (ANS.arr[i][j] ? '+' : '-');
		}
		cout << '\n';
	}
}


main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
	cin >> t;
	while(t--){
		solve();
	}

	return 0;
}

Compilation message

stones.cpp:157:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  157 | main(){
      | ^~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 8 ms 324 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 452 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 8 ms 324 KB Output is correct
3 Correct 4 ms 452 KB Output is correct
4 Correct 10 ms 456 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 1580 KB Output is correct
2 Correct 142 ms 11444 KB Output is correct
3 Correct 138 ms 12576 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 1712 KB Output is correct
2 Correct 139 ms 9144 KB Output is correct
3 Correct 117 ms 6080 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 8 ms 324 KB Output is correct
3 Correct 4 ms 452 KB Output is correct
4 Correct 10 ms 456 KB Output is correct
5 Correct 156 ms 1580 KB Output is correct
6 Correct 142 ms 11444 KB Output is correct
7 Correct 138 ms 12576 KB Output is correct
8 Correct 149 ms 1712 KB Output is correct
9 Correct 139 ms 9144 KB Output is correct
10 Correct 117 ms 6080 KB Output is correct
11 Correct 41 ms 572 KB Output is correct
12 Correct 123 ms 7892 KB Output is correct
13 Correct 130 ms 5836 KB Output is correct
14 Correct 107 ms 3596 KB Output is correct
15 Correct 165 ms 17088 KB Output is correct
16 Correct 119 ms 12600 KB Output is correct
17 Correct 56 ms 5740 KB Output is correct