oj.uz

Submission #684031

# Submission time Handle Problem Language Result Execution time Memory
684031 2023-01-20T04:49:09 Z dostigator Red-blue table (IZhO19_stones) C++17
54 / 100
 25 ms 1252 KB 
//izho gold
#include <bits/stdc++.h>

using namespace std;

#define all(a) a.begin(),a.end()
#define pb push_back
#define vt vector
#define endl '\n'
#define Y second
#define X first
typedef long long ll;
typedef long double ld;
const ll mod=1e9+7;
const ll INF=1e18;
const int inf=1e9;
const int N=2e5+505;
const int M=1e3+10;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};

int n,m;

void solve(){
	cin>>n>>m;
	if(min(n,m)<=3){
		if(n<=m){
			if(n==1){
				cout<<m<<endl;
				for(int i=1; i<=m; ++i)cout<<'-';
				cout<<endl;
				return;
			}if(n==2){
				cout<<m<<endl;
				for(int i=1; i<=m; ++i)cout<<'-';
				cout<<endl;
				for(int i=1; i<=m; ++i)cout<<'-';
				cout<<endl;
				return;
			}if(n==3){
				cout<<m+1<<endl;
				for(int i=1; i<=m; ++i)cout<<'-';
				cout<<endl;
				for(int i=1; i<=m; ++i)cout<<'+';
				cout<<endl;
				for(int i=1; i<=m; ++i)cout<<'-';
				cout<<endl;
				return;
			}
		}else{
			if(m==1){
				cout<<n<<endl;
				for(int i=1; i<=n; ++i)cout<<"+\n";
				return;
			}if(m==2){
				cout<<n<<endl;
				for(int i=1; i<=n; ++i)cout<<"++\n";
				return;
			}if(m==3){
				cout<<n+1<<endl;
				for(int i=1; i<=n; ++i)cout<<"+-+\n";
				return;
			}
		}
	}if(min(n,m)<=5){
		char matrix[n+1][m+1];
		for(int i=1; i<=n; ++i)for(int j=1; j<=m; ++j)matrix[i][j]='-';
		if(n<m){
			if(n==4){
				for(int i=1; i<=n; ++i)for(int j=1; j<=m; ++j){
					if(i==3)matrix[i][j]='+';
				}cout<<m+1<<endl;
				for(int i=1; i<=n; ++i)for(int j=1; j<=m; ++j){
					cout<<matrix[i][j];
					if(j==m)cout<<endl;
				}return;
			}
			cout<<n-2+m<<endl;
			for(int i=1; i<=n; ++i){
				for(int j=1; j<=m; ++j){
					if(i<=2)matrix[i][j]='-';
					else{
						if(n==5 && j%3==1 && i!=3) matrix[i][j]='+';
						if(n==5 && j%3==2 && i!=5) matrix[i][j]='+';
						if(n==5 && j%3==0 && i!=4) matrix[i][j]='+';
						if(n==4 && j%2 && i==4)matrix[i][j]='+';
						if(n==4 && j%2==0 && i==3)matrix[i][j]='+';
					}
				}
			}
		}else{
			if(m==4) {
				cout<<n+1<<endl;
				for(int i=1; i<=n; ++i)for(int j=1; j<=m; ++j){
					if(j==1 || j==m || j==3)matrix[i][j]='+';
				}for(int i=1; i<=n; ++i)for(int j=1; j<=m; ++j){
					cout<<matrix[i][j];
					if(j==m)cout<<endl;
				}return;
			}
			cout<<m-2+n<<endl;
			for(int i=1; i<=n; ++i){
				for(int j=1; j<=m; ++j){
					if(j<=2)matrix[i][j]='+';
					else {
						if(m==5 && i%3==1 && j==3)matrix[i][j]='+';
						if(m==5 && i%3==2 && j==4)matrix[i][j]='+';
						if(m==5 && i%3==0 && j==5)matrix[i][j]='+';
				//		if(m==4 && i%2 && j==4) matrix[i][j]='+';
				//		if(m==4 && i%2==0 && j==3) matrix[i][j]='+';
					}
				}
			}
		}for(int i=1; i<=n; ++i){
			for(int j=1; j<=m; ++j){
				cout<<matrix[i][j];
			}cout<<endl;
		}return;
	}
	if(n%2==m%2 && n%2==0){
		int cnt=n;
		char matrix[n+2][m+2];
		for(int i=1; i<=n; ++i)for(int j=1; j<=n; ++j)matrix[i][j]='#';
		int dep=(n/2-1)/2;
		for(int i=n/2; i<=n; ++i){
			matrix[i][n/2]='-';
			matrix[i][n/2+1]='-';
		}
		for(int i=1; i<n/2; ++i){
			++cnt;
			int l=1,r=n;
			if(i%2) r=n/2+1;
			else l=n/2;
			for(int j=1; j<=n; ++j){
				if(j>=l && j<=r) matrix[i][j]='+';
				else matrix[i][j]='-';
			}
		}int L=n/2,w=2;
		while(dep>0){
			int cnt2=0;
			w*=3;
		//	cout<<dep<<' '<<L<<endl;
			for(int i=L; i<L+dep; ++i){//mb >n
				++cnt2;
				++cnt;
				int cnt3=n/2+1;
				if(i%2){
					for(int j=1; j<=m; ++j){
						if(matrix[i][j]=='-')continue;
						if(cnt3<=0) matrix[i][j]='-';
						else matrix[i][j]='+';
						--cnt3;
					}continue;
				}for(int j=m; j>=1; --j){
					if(matrix[i][j]=='-'){
						//cout<<"hi "<<j<<endl;
						continue;
					}
					if(cnt3<=0)matrix[i][j]='-';
					else matrix[i][j]='+';
					--cnt3;
				}
			}if(cnt2==0)break;
			L+=dep;
			cnt2/=2;
			dep=(n/2-1)-(((L-1)+1)/2);
			++dep;
			if(n-w<(n/2)+1){
				break;
			}
			for(int i=L; i<=n; ++i){
				for(int j=n/2-(w/2)+1; j<=n/2+(w/2); ++j)matrix[i][j]='-';
			}//break;
		}for(int i=L; i<=n; ++i){
			for(int j=1; j<=n; ++j)matrix[i][j]='-';
		}cout<<cnt<<endl;
		for(int i=1; i<=n; ++i)for(int j=1; j<=m; ++j){
			cout<<matrix[i][j];
			if(j==m)cout<<endl;
		}return;
	}
	if(n%2==m%2 && n%2==1){
		cout<<n+m-2<<endl;
		for(int i=1; i<n; ++i)for(int j=1; j<=m; ++j){
			if(j==m){
				cout<<'+'<<endl;
				continue;
			}if(i%2){
				if(j%2)cout<<'-';
				else cout<<'+';
			}else{
				if(j%2)cout<<'+';
				else cout<<'-';
			}
		}
		for(int i=1; i<=m; ++i){
			cout<<'-';
		}cout<<endl;
		return;
	}
	if(n*m<=36){
		vt<pair<int,int>>lst;
		char matrix[20][20];
		for(int mask=0; mask<(1<<(n*m)); ++mask){
			int x=1,y=1;
			for(int i=0; i<n*m; ++i){
				if(mask&(1<<i)){
					matrix[x][y]='+';
				}else matrix[x][y]='-';
				++y;
				if(y>m){
					++x;
					y=1;
				}
			}
			int cnt=0;
			for(int i=1; i<=n; ++i){
				int heh=0;
				for(int j=1; j<=m; ++j)heh+=(matrix[i][j]=='+');
				if(heh>m-heh)++cnt;
			}for(int j=1; j<=m; ++j){
				int heh=0;
				for(int i=1; i<=n; ++i)heh+=(matrix[i][j]=='-');
				if(heh>n-heh)++cnt;
			}lst.pb({cnt,mask});
		}sort(all(lst));
		int mask=lst.back().Y;
		cout<<lst.back().X<<endl;
		int x=1,y=1;
		for(int i=0; i<n*m; ++i){
			if(mask&(1<<i)){
				matrix[x][y]='+';
			}else matrix[x][y]='-';
			++y;
			if(y>m){
				++x;
				y=1;
			}
		}
		for(int i=1; i<=n; ++i){
			for(int j=1; j<=m; ++j){
				cout<<matrix[i][j];
			}cout<<endl;
		}return;
	}
}

int main(){
	//srand(time(0));
	//freopen("hotel.in","r",stdin);
	//freopen("hotel.out","w",stdout);
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int tt=1,lolol=0;
	cin>>tt;
	while(tt--) {
		//cout<<"Case "<<++lolol<<": ";
		solve();
	}
}

Compilation message

stones.cpp: In function 'int main()':
stones.cpp:253:11: warning: unused variable 'lolol' [-Wunused-variable]
  253 |  int tt=1,lolol=0;
      |           ^~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 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 1 ms 316 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 2 ms 340 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1216 KB Output is correct
2 Correct 25 ms 1212 KB Output is correct
3 Correct 18 ms 1108 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 1252 KB in the table A+B is not equal to 44
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 22 ms 1216 KB Output is correct
6 Correct 25 ms 1212 KB Output is correct
7 Correct 18 ms 1108 KB Output is correct
8 Incorrect 22 ms 1252 KB in the table A+B is not equal to 44
9 Halted 0 ms 0 KB -