QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#390124 | #2651. Pixels | kevinyang# | AC ✓ | 150ms | 8848kb | C++17 | 3.3kb | 2024-04-15 06:01:00 | 2024-04-15 06:01:01 |
Judging History
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