oj.uz

Submission #690833

# Submission time Handle Problem Language Result Execution time Memory
690833 2023-01-30T12:54:47 Z OrazB Red-blue table (IZhO19_stones) C++14
100 / 100
 204 ms 9096 KB 
#include <bits/stdc++.h>
#define N 1005
#define wr cout << "Continue debugging\n";
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pii pair <int, int>
#define pb push_back
#define ff first
#define ss second
using namespace std;
 
int t, c[N], mx, mxb, n, m, a[N][N], b[N][N];
 
void bit(int x, int cur){
	if (x == cur+1){
		int cnt = 0;
		if (n == cur){
			for (int i = 1; i <= n; i++){
				for (int j = 1; j <= m; j++){
					a[i][j] = 0;
				}
			}
			priority_queue<pii> q;
			for (int i = 1; i <= m; i++){
				q.push({0, i});
			}		
			for (int i = 1; i <= n; i++){
				if (!c[i]) continue;
				cnt++;
				int x = m/2+1;
				while(x--){
					int val = q.top().ff;
					int j = q.top().ss;
					q.pop();
					a[i][j] = 1;
					q.push({val-1, j});
				}
			}
			for (int i = 1; i <= m; i++){
				int num = 0;
				for (int j = 1; j <= n; j++){
					if (!a[j][i]) num++;
				}
				if (num >= n/2+1) cnt++;
			}
		}else{
			for (int i = 1; i <= n; i++){
				for (int j = 1; j <= m; j++){
					a[i][j] = 1;
				}
			}
			priority_queue<pii> q;
			for (int i = 1; i <= n; i++){
				q.push({0, i});
			}		
			for (int i = 1; i <= m; i++){
				if (!c[i]) continue;
				cnt++;
				int x = n/2+1;
				while(x--){
					int val = q.top().ff;
					int j = q.top().ss;
					q.pop();
					a[j][i] = 0;
					q.push({val-1, j});
				}
			}
			for (int i = 1; i <= n; i++){
				int num = 0;
				for (int j = 1; j <= m; j++){
					if (a[i][j]) num++;
				}
				if (num >= m/2+1) cnt++;
			}
		}
		if (mx < cnt){
			mx = cnt;
			for (int i = 1; i <= n; i++){
				for (int j = 1; j <= m; j++){
					b[i][j] = a[i][j];
				}
			}
		}
		return;
	}
	for (int i = 0; i < 2; i++){
		c[x] = i;
		bit(x+1, cur);
	}
}
 
int main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> t;
	while (t--){
		mx = mxb = 0;
		cin >> n >> m;
		if (min(n,m) <= 5){
			bit(1, min(n, m));
			cout << mx << '\n';
			for (int i = 1; i <= n; i++){
				for (int j = 1; j <= m; j++){
					if (b[i][j]) cout << '+';
					else cout << '-';
				}
				cout << '\n';
			}
			continue;
		}
		for (int i = 1; i <= n; i++){
			for (int j = 1; j <= m; j++){
				a[i][j] = 0;
				b[i][j] = 1;
			}
		}
		priority_queue<pii> q;
		for (int i = 1; i <= m; i++){
			q.push({n, i});
		}
		int idx = 0, cur = m;
		mx = m;
		for (int i = 1; i <= n; i++){
			int x = m/2+1;
			while(x--){
				int val = q.top().ff;
				int j = q.top().ss;
				q.pop();
				if (val == n/2+1) cur--;
				q.push({val-1, j});
			}
			if (mx < i+cur){
				mx = i+cur;
				idx = i;
			}
		}
		while(!q.empty()){
			q.pop();
		}
		for (int i = 1; i <= m; i++){
			q.push({n, i});
		}		
		for (int i = 1; i <= idx; i++){
			int x = m/2+1;
			while(x--){
				int val = q.top().ff;
				int j = q.top().ss;
				q.pop();
				a[i][j]=1;
				q.push({val-1, j});
			}
		}
		//
		while(!q.empty()){
			q.pop();
		}
		for (int i = 1; i <= n; i++){
			q.push({m, i});
		}
		cur = mxb = n;
		idx = 0;
		for (int i = 1; i <= m; i++){
			int x = n/2+1;
			while(x--){
				int val = q.top().ff;
				int j = q.top().ss;
				q.pop();
				if (val == m/2+1) cur--;
				q.push({val-1, j});
			}
			if (mxb < i+cur){
				mxb = i+cur;
				idx = i;
			}
		}
		// cout << mxb;
		while(!q.empty()){
			q.pop();
		}
		for (int i = 1; i <= n; i++){
			q.push({m, i});
		}		
		for (int i = 1; i <= idx; i++){
			int x = n/2+1;
			while(x--){
				int val = q.top().ff;
				int j = q.top().ss;
				q.pop();
				b[j][i]=0;
				q.push({val-1, j});
			}
		}
		cout << max(mxb, mx) << '\n';
		for (int i = 1; i <= n; i++){
			for (int j = 1; j <= m; j++){
				int x = b[i][j];
				if (mxb < mx) x = a[i][j];
				if (x) cout << '+';
				else cout << '-';
			}
			cout << '\n';
		}	
	}
}

Subtask #1
17.0 / 17.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 324 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 4 ms 748 KB Output is correct
4 Correct 12 ms 724 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 2116 KB Output is correct
2 Correct 139 ms 7028 KB Output is correct
3 Correct 124 ms 8624 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 2352 KB Output is correct
2 Correct 117 ms 6756 KB Output is correct
3 Correct 112 ms 5580 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 324 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 4 ms 748 KB Output is correct
4 Correct 12 ms 724 KB Output is correct
5 Correct 148 ms 2116 KB Output is correct
6 Correct 139 ms 7028 KB Output is correct
7 Correct 124 ms 8624 KB Output is correct
8 Correct 128 ms 2352 KB Output is correct
9 Correct 117 ms 6756 KB Output is correct
10 Correct 112 ms 5580 KB Output is correct
11 Correct 29 ms 724 KB Output is correct
12 Correct 113 ms 7376 KB Output is correct
13 Correct 123 ms 8256 KB Output is correct
14 Correct 89 ms 6820 KB Output is correct
15 Correct 204 ms 9096 KB Output is correct
16 Correct 107 ms 7244 KB Output is correct
17 Correct 47 ms 5896 KB Output is correct