oj.uz

Submission #961183

# Submission time Handle Problem Language Result Execution time Memory
961183 2024-04-11T16:09:45 Z pcc Red-blue table (IZhO19_stones) C++17
100 / 100
 524 ms 5336 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

bool trivial(int r,int c){
	if(r == 1){
		cout<<c<<'\n';
		for(int i = 0;i<c;i++)cout<<'-';
		cout<<'\n';
		return true;
	}
	else if(c == 1){
		cout<<r<<'\n';
		for(int i = 0;i<r;i++)cout<<'+'<<'\n';
		return true;
	}
	else if(r == 2){
		cout<<c<<'\n';
		for(int i = 0;i<r;i++){
			for(int j = 0;j<c;j++)cout<<'-';
			cout<<'\n';
		}
		return true;
	}
	else if(c == 2){
		cout<<r<<'\n';
		for(int i = 0;i<r;i++){
			for(int j = 0;j<c;j++)cout<<'+';
			cout<<'\n';
		}
		return true;
	}
	else return false;
}

namespace S1{

	int ans[22][22],C[22][22];
	int row[22],col[22];

	void calc(int r,int c){
		int big = 0,cnt = 0;
		for(int i = 0;i<(1<<(r*c));i++){
			for(int j = 0;j<r;j++)row[j] = 0;
			for(int j = 0;j<c;j++)col[j] = 0;
			for(int j = 0;j<r;j++){
				for(int k = 0;k<c;k++){
					if(i&(1<<(j*c+k)))row[j]++,col[k]++;
				}
			}
			int tc = 0;
			for(int j = 0;j<r;j++){
				tc += (row[j]>c-row[j]);
			}
			for(int j = 0;j<c;j++){
				tc += (r-col[j]>col[j]);
			}
			if(tc>cnt)cnt = tc,big = i;
		}
		ans[r][c] = cnt;
		C[r][c] = big;
	}

	void prep(){
		for(int i = 1;i<=5;i++){
			for(int j = 1;i*j<=20;j++)calc(i,j);
		}
		return;
	}

	void solve(int r,int c){
		if(trivial(r,c))return;
		string s[r];
		for(int i = 0;i<r;i++){
			for(int j = 0;j<c;j++){
				if(C[r][c]&(1<<(i*c+j)))s[i] += '+';
				else s[i] += '-';
			}
		}
		cout<<ans[r][c]<<'\n';
		for(auto &i:s)cout<<i<<'\n';
		return;
	}
}

namespace FULL{
	void solve(int r,int c){
		int c1 = ((r+1)/2-1)*c/(c/2+1);
		int c2 = ((c+1)/2-1)*r/(r/2+1);
		vector<vector<int>>v(r,vector<int>(c,-1));
		if(c1+c>c2+r){
			int now = 0;
			for(int i = 0;i<c1;i++){
				for(int j = 0;j<(c/2+1);j++)v[i][(now+j)%c] = 1;
				now = (now+(c/2+1))%c;
			}
		}
		else{
			for(auto &i:v)for(auto &j:i)j = 1;
			int now = 0;
			for(int i = 0;i<c2;i++){
				for(int j = 0;j<(r/2+1);j++)v[(now+j)%r][i] = -1;
				now = (now+(r/2+1))%r;
			}
		}
		cout<<max(c1+c,c2+r)<<'\n';
		for(auto &i:v){
			for(auto &j:i)cout<<(j==1?'+':'-');
			cout<<'\n';
		}
		return;
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	S1::prep();
	int t;
	cin>>t;
	while(t--){
		int r,c;
		cin>>r>>c;
		if(trivial(r,c));
		else if(r<=4&&c<=4)S1::solve(r,c);
		else FULL::solve(r,c);
	}
	return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 428 KB Output is correct
2 Correct 490 ms 428 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 432 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 428 KB Output is correct
2 Correct 490 ms 428 KB Output is correct
3 Correct 486 ms 432 KB Output is correct
4 Correct 488 ms 428 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 1456 KB Output is correct
2 Correct 503 ms 3584 KB Output is correct
3 Correct 515 ms 3996 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 510 ms 1460 KB Output is correct
2 Correct 524 ms 3060 KB Output is correct
3 Correct 512 ms 2228 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 428 KB Output is correct
2 Correct 490 ms 428 KB Output is correct
3 Correct 486 ms 432 KB Output is correct
4 Correct 488 ms 428 KB Output is correct
5 Correct 524 ms 1456 KB Output is correct
6 Correct 503 ms 3584 KB Output is correct
7 Correct 515 ms 3996 KB Output is correct
8 Correct 510 ms 1460 KB Output is correct
9 Correct 524 ms 3060 KB Output is correct
10 Correct 512 ms 2228 KB Output is correct
11 Correct 495 ms 684 KB Output is correct
12 Correct 511 ms 2904 KB Output is correct
13 Correct 494 ms 2120 KB Output is correct
14 Correct 510 ms 1376 KB Output is correct
15 Correct 520 ms 5336 KB Output is correct
16 Correct 508 ms 4020 KB Output is correct
17 Correct 500 ms 1968 KB Output is correct