QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#390124#2651. Pixelskevinyang#AC ✓150ms8848kbC++173.3kb2024-04-15 06:01:002024-04-15 06:01:01

Judging History

This is the latest submission verdict.

  • [2024-04-15 06:01:01]
  • Judged
  • Verdict: AC
  • Time: 150ms
  • Memory: 8848kb
  • [2024-04-15 06:01:00]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
vector<int>dx = {-1,0,1,0,0};
vector<int>dy = {0,1,0,-1,0};
bool good(int x, int y){
	return x>=1 && x<=n && y>=1 && y<=m;
}
void apply(vector<vector<int>>&a, int x, int y){
	for(int d = 0; d<5; d++){
		int nx = dx[d]+x;
		int ny = dy[d]+y;
		if(!good(nx,ny)){
			continue;
		}
		a[nx][ny]^=1;
	}
}
void mxor(vector<int>&a, vector<int>b){
	for(int i = 0; i<a.size(); i++){
		a[i]^=b[i];
	}
}
vector<int> rxor(vector<int>a, vector<int>b){
	for(int i = 0; i<a.size(); i++){
		a[i]^=b[i];
	}
	return a;
}
bool bad = false;
vector<vector<int>> solve(vector<vector<int>>a){
	vector<vector<int>>ans(n+1,vector<int>(m+1));
	for(int i = 2; i<=n; i++){
		for(int j = 1; j<=m; j++){
			if(a[i-1][j]){
				apply(a,i,j);
				ans[i][j]^=1;
			}
		}
	}
	vector<vector<int>>arr(m+1,vector<int>(2*m+1));
	for(int j = 1; j<=m; j++){
		vector<vector<int>>b(n+1,vector<int>(m+1));
		apply(b,1,j);
		for(int i = 2; i<=n; i++){
			for(int j = 1; j<=m; j++){
				if(b[i-1][j]){
					apply(b,i,j);

				}
			}
		}
		for(int i = 1; i<=m; i++){
			arr[j][i] = b[n][i];
		}
		arr[j][m+j] = 1;
	}
	int cur = 1;
	vector<vector<int>>basis(m+1);
	for(int i = 1; i<=m; i++){
		sort(arr.begin()+1,arr.end());
		reverse(arr.begin()+1,arr.end());
		if(arr[cur][i]!=1)continue;
		for(int j = 1; j<=m; j++){
			if(j==cur)continue;
			if(arr[j][i] == 1){
				mxor(arr[j],arr[cur]);
			}
		}
		cur++;
	}
	for(int i = 1; i<=m; i++){
		int fst = 0;
		for(int j = 1; j<=m; j++){
			if(arr[i][j]){
				fst = j;
				break;
			}
		}
		if(fst==0)continue;
		basis[fst] = arr[i];
	}
	vector<int>res(2*m+1);
	for(int j = 1; j<=m; j++){
		res[j] = a[n][j];
	}
	for(int j = 1; j<=m; j++){
		if(res[j]){
			if(basis[j].size()){
				mxor(res,basis[j]);
			}
			else{
				bad = true;
				return ans;
			}
		}
	}
	bool found = true;
	for(int j = 1; j<=m; j++){
		if(res[j]){
			bad = true;
			return ans;
		}
	}
	for(int j = m+1; j<=2*m; j++){
		if(!res[j])continue;
		apply(a,1,j-m);
		ans[1][j-m]^=1;
	}
	for(int i = 2; i<=n; i++){
		for(int j = 1; j<=m; j++){
			if(a[i-1][j]){
				apply(a,i,j);
				ans[i][j]^=1;
			}
		}
	}
	for(int j = 1; j<=m; j++){
		if(a[n][j])bad = true;
	}
	return ans;
}
signed main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	cin >> n >> m;
	if(n>=m){
		vector<vector<int>>arr(n+1,vector<int>(m+1));
		for(int i = 1; i<=n; i++){
			for(int j = 1; j<=m; j++){
				char ch;
				cin >> ch;
				if(ch == 'B'){
					arr[i][j] = 1;
				}
			}
		}
		auto res = solve(arr);
		if(bad){
			cout << "IMPOSSIBLE\n";
			return 0;
		}
		for(int i = 1; i<=n; i++){
			for(int j = 1; j<=m; j++){
				if(res[i][j])cout << 'P';
				else cout << 'A';
				if(j<m)cout << ' ';
			}
			cout << '\n';
		}
	}
	else{
		swap(n,m);
		vector<vector<int>>arr(n+1,vector<int>(m+1));
		for(int j = 1; j<=m; j++){
			for(int i = 1; i<=n; i++){
				char ch;
				cin >> ch;
				if(ch=='B'){
					arr[i][j] = 1;
				}
			}
		}
		auto res = solve(arr);
		if(bad){
			cout << "IMPOSSIBLE\n";
			return 0;
		}
		for(int i = 1; i<=m; i++){
			for(int j = 1; j<=n; j++){
				if(res[j][i])cout << 'P';
				else cout << 'A';
				if(j<n)cout << ' ';
			}
			cout << '\n';
		}
	}
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3604kb

input:

1 2
B W

output:

IMPOSSIBLE

result:

ok 

Test #2:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

5 22
B B B W B W W W B W B B B W B B B B W B B B
B W W W B W W W B W B W W W B W W B W B W W
B B B W B W B W B W B B B W B B B B W B W W
W W B W B W B W B W B W W W B W B W W B W W
B B B W W B W B W W B B B W B W W B W B B B

output:

A P P A P P A A P A A P P P A A P A P A P A
A P P A P A P P A P A P A A A A A P P P A A
A P P A P P A A A P P A A P P A A P A P A A
A A A A A A P P A P P P A A P A A P P P P A
A P A A A A P A P P P A P A P P A P P P A P

result:

ok 

Test #3:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

1 2
B B

output:

A P

result:

ok 

Test #4:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

4 4
B B W W
B B W B
B B W B
W B W B

output:

A A A A
P P A A
P P P P
A P P P

result:

ok 

Test #5:

score: 0
Accepted
time: 0ms
memory: 3888kb

input:

4 4
B B W W
B B W B
B B W W
W B W B

output:

IMPOSSIBLE

result:

ok 

Test #6:

score: 0
Accepted
time: 0ms
memory: 3728kb

input:

4 200
B B B W B B W B B B B W B W W W W W B W W B W B W B B W W W W B B B B W W W B B B B B B B B B B W B W B W W W W B B W W W W B W B W B W W W W W W W B B W W B W W W W W W W B W W B B W B W B B W B W B W B W B W B W W W B W W B B W B W W W B B W B B W B B W B W W B B B B B W W B B B W W W B W W ...

output:

P P A P P P P P A A P P A P A P A P A A A A P A A A P P A A A A A P P A P P P P P P P P A A P A P P A P P A A A P P P P P P A A P A P A P P A P P P P A P P A P P A A P A A P P P P A A A P P P A P P A P P P P P P P A A A A P P A A P A P A A A P P P P A A A A P A P A A P A P P A P A P A P P P P P P A ...

result:

ok 

Test #7:

score: 0
Accepted
time: 0ms
memory: 3952kb

input:

40 200
B B W B W W W W W B W B W B W B B W W B W W W B W W W B W B B B W W W B B B B W W W B W B B W W W W W B W W W W W W B W W B W W W W B B W W W B W B W B B B W W B W W B W W B B W B W B B B W W B B W B W B W B B B B B B W B W B B B W B B B B W W W B B W B B B W W W W B B B B B W W B W B W B B B...

output:

A P P P A P A P A A P A A A A P P P A A P P A A P P P P P P P A A P P A P A P P A A A A A A A P P P P P A P A P A P P A A A P P P P A P P A A A A P A P P P A A P P A A P A A A A A A P P A A A P P P P A P A A P A A A A P A P P P P A P A P A A A P A A A P P P A P P A A A A P P A P P P A A A A A P P P ...

result:

ok 

Test #8:

score: 0
Accepted
time: 48ms
memory: 5244kb

input:

200 200
W W W W W B B W B B W W B B W B W B W W W B W W B B B W W W B W W B B B B W B W B B B B B W W B W B W W B W B B W B B B W W B B B W B W W W W W W W B B W B W B W W B W W B B B B B B W W W W B W B W W B B B B W B B B W W W W B W B W W B W B B B W B W B B W W B B B B B B W B W B B W W B B B B ...

output:

A A A P P P A A A A P A P A P P A P A P P A A P P A P A A P P P P P P A P P A P P P A A P P P A P A A A A P A P A A P P P A P A P A A P P P A A A A A P A A A A A A A A P P P P P A A P P P A A A P A P P A A A A P A A P P A A P A P P A A P A P P A A P P A A P P A A P A A P P A A A P P A A P P A P A A ...

result:

ok 

Test #9:

score: 0
Accepted
time: 68ms
memory: 6688kb

input:

250 250
W B B W W W W W B B W B B B B W B W B W W W W W B W W B B W B B B W W B W W B B B W W B W B W W W B W B W W W W B B W B B B B W B B W B W W B W B W B B W W W B W W B B W B W W W W W W B B B W B W B B B W W W B W W W W W W B B B B B B W B B W W W W W W W B B W B B B W B B B W B B W W W B W W ...

output:

P P A A P A A A P A A P P P A A P P P A A A P A P A P P P P P P P P P P P P P A A A P P P P P A P A P P A P A A A P A P A P A A A P A P P P A P P P A A A A A A A P A P P A A P P A A P A A A A A P P P A P A A A P P P P P P P A P P P P A A P A P A P A A P P A A P P A P A A A A A A P A P P P P P A P P ...

result:

ok 

Test #10:

score: 0
Accepted
time: 1ms
memory: 3964kb

input:

4 250
W B W W B W B W W B W B W B B W W B W W W B B B B W W B W B W W B W W B B B W W B W B B B B W B B B W W B W W W W W W W W W W W B W B B B B W B W B W B W W W B W W W W W B B W B B W W W B B B W B W B B W W W B B W B W B B B W W W W B B W W B B B W W W B B B W W W B B B W W B B B B B W B B W B ...

output:

P A P A A A A P A P P A P A P A P P A A A P P A P P A A A A A P A A A P P P A P P A P P P A P P P A A A P A P A P P P A A P A A A P A A A P P P A P P P P A A P A P A A P P P P A P P A P P P P P P P A P P P P A A P A A A P A P P P A P A P P A A P A A A P A A P A A P A A A P P P P A P A A P P A P P A ...

result:

ok 

Test #11:

score: 0
Accepted
time: 1ms
memory: 3932kb

input:

250 4
B W B W
W B W W
W B W B
W B W B
B B W B
B W W W
B W W W
W B B B
B B W W
B W B W
B B W B
W W W W
B W B B
B W B B
W B W W
W W B B
B B B B
W B B W
W W B B
B W B W
B W B W
B W W W
B B B B
W W B W
W W W W
W W W W
W W W B
B B B W
W W B W
W B B B
W B W B
W W B W
B W B B
W W B B
W B B W
W B B B
B W W ...

output:

A P P P
A A A A
A A P P
A A A P
A P A P
A A A P
P P P A
P P A A
P A P P
P A A A
P P A P
A P A A
A A P P
P A P P
A A A A
P P P P
A P A P
P P A P
A A P A
P A A P
A P P P
P A A P
A A A A
A P P A
P A P P
P P P A
P P P A
P A P A
P A P P
A A A A
P P A A
A P P P
A P A A
A A P A
A A A A
A P A A
P A A P
A A ...

result:

ok 

Test #12:

score: 0
Accepted
time: 3ms
memory: 4900kb

input:

5000 4
B B B W
W B W W
B B W W
W W W B
W W B W
W B W B
W W B W
W B W B
W B W B
W W B W
W W B W
B B B B
B W W W
W B B W
B W B B
B W W W
B B W W
B B W W
B W W B
B B W W
W B B W
W B B W
B B B W
B B W W
W B B B
B W W W
B W B W
B W B B
B B W B
B W W B
W W B W
B B W B
W W B B
B B W W
W B B W
B W W B
B B W...

output:

A P P A
A P P P
P A A A
A P P P
A A P P
A A A P
A P A P
P P P A
A P A P
A P P A
P P P A
A A A P
A A P A
P P P A
A A A P
A P P A
A A A A
P A P A
A P P P
P A A P
A P A A
A A A P
A A A P
P P A A
P P P P
P P A P
A P P A
P P P A
P A A A
P P P P
A P P P
A P P P
A A A A
A P A A
A A P A
A P A P
A P P A
A A ...

result:

ok 

Test #13:

score: 0
Accepted
time: 16ms
memory: 7112kb

input:

5000 20
B W W W W W W B W W B B W B W B B W W W
B B B W W W W W W B B W B B B W W W B W
W W W W W B W B W B B W W W W B W B W B
B W W B W W B W W W W B W B W B W B W B
W B W B W B B W B B B B B B B B W W W B
W W B B B W W W W W W W B W W W W W W B
W B B W B B W B B B W B B W W W B B W B
B W W W W B ...

output:

A A A A P A A A A A P A P P P P A A A P
P A A P P P A P A P A P A A P P A A P P
A A A A A A A P A A A P P P A P P P P P
P A A P P A P P P A A P P A P A P A A A
A P P P A A P A A P P A P A P A A P P A
A P P A A A P A P P P A P P P A A A A A
P P A P P P A A A A P A A P P P A P P P
A A A A A P A P A P ...

result:

ok 

Test #14:

score: 0
Accepted
time: 62ms
memory: 6620kb

input:

1000 100
W W B B B W B B B W W W B B W B B W B W B W W W B W W B W B W W W B B W W B W W B B B W W W B W B B B W W B W W W B B B B B W B B B W B B W B W W B W B W W W B B B W B B W B B B B W B B B W B B B W B
B B B B B B W W B W B B W W B B W B B B W B W B W B W B B B B B W W W W W B W B B W W W W B...

output:

A A A P A A P P P A A P P P A P P P P P P A A A A P P A A A P A A P P P P P P A P A P P A P A A P A A A P A A P P P P P P A P P P A P A A A P A P A A A P A A P P P A A A P A P P A A A P P A A P P P A
A A A A A P P A P P P A A P A P A P A P P P A A A A A A A A P P P P A P P A A A A P P A A P A P A A ...

result:

ok 

Test #15:

score: 0
Accepted
time: 111ms
memory: 7604kb

input:

250 400
W W W W W W B W B W W B B B B W W W B W W B B B W W B W B W B W W W B B W W W B B B B W W W B B B B W B W W B B W W W B B B W B W B B B B W B W W B B W B W B W B W B B B B B W W W W W B B W W B W B B W W W B B B B W W W W W B B W W B W W B B B B W W B W W W B W W W B W B B W B W B W W B B W ...

output:

A A P A A A P P A P A P A A A P A P P A A A P A P P A P P A P P A P A P A P A P P P P A A A P A P A A A P P P A P A A P P A A P P P A P A P P A P P P A P A P A A A A A A A A P P P A P A P A P A A P P P P A A P A A A A P A P A A P A A A P A A A A P P P P P P A A A P P P A A P P P A P A A P P A A P P ...

result:

ok 

Test #16:

score: 0
Accepted
time: 150ms
memory: 8848kb

input:

316 316
B W W B B W B W B W B B W W W B W B W W W W B W B B W B W B B W W B B B B W W B W W B B W B W W B W B B B B W B B B W B B W B W B W W W B W B W W B W B B W W W B B B B B B B W W W B B W W W W B B B B W B W W W W W B B B W W B W B W B B B W W W W W B W B B B B B B B B B B W W W W B W B W B B ...

output:

P P A A P P P A P P A A P A A P P A P P P P P P A A A A P P A A P A P A P A A A A A P P P A P A A A A P P P P A A P A A A P A P P P P A P P A A P A A A A A A A P A A A A A A A P A P P P P A A P P P P A P P P A A P A A P A A A P P P A P P A P P P A A A A P A P P A A P A P A P P A P A A A A P A A P P ...

result:

ok