제출 #690833

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
690833		OrazB	Red-blue table (IZhO19_stones)	C++14	100 / 100	204 ms	9096 KiB

stones

#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 / 17
• Subtask 2: 10 / 10
• Subtask 3: 16 / 16
• Subtask 4: 11 / 11
• Subtask 5: 15 / 15
• Subtask 6: 31 / 31