QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#367740#5070. Check Pattern is Badbear0131TL 76ms3712kbC++144.1kb2024-03-26 12:52:442024-03-26 12:52:44

Judging History

你现在查看的是最新测评结果

  • [2024-03-26 12:52:44]
  • 评测
  • 测评结果:TL
  • 用时:76ms
  • 内存:3712kb
  • [2024-03-26 12:52:44]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef array<int, 3> ai3;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const int Mod = 998244353;
inline int sign(int a){ return (a&1) ? (Mod-1) : 1; }
inline void uadd(int &a, int b){ a += b-Mod; a += (a>>31) & Mod; }
inline void usub(int &a, int b){ a -= b, a += (a>>31) & Mod; }
inline void umul(int &a, int b){ a = (int)(1ll * a * b % Mod); }
inline int add(int a, int b){ a += b-Mod; a += (a>>31) & Mod; return a; }
inline int sub(int a, int b){ a -= b, a += (a>>31) & Mod; return a; }
inline int mul(int a, int b){ a = (int)(1ll * a * b % Mod); return a; }
int qpow(int b, ll p){ int ret = 1; while(p){ if(p&1) umul(ret, b); umul(b, b), p >>= 1; } return ret; }
const int fN = 1010;
int fact[fN], invfact[fN], pw2[fN], invpw2[fN], inv[fN];
void initfact(int n){
	pw2[0] = 1; for(int i = 1; i <= n; ++i) pw2[i] = mul(pw2[i-1], 2);
	invpw2[0] = 1; for(int i = 1; i <= n; ++i) invpw2[i] = mul(invpw2[i-1], (Mod+1) / 2);
	fact[0] = 1; for(int i = 1; i <= n; ++i) fact[i] = mul(fact[i-1], i);
	invfact[n] = qpow(fact[n], Mod-2); for(int i = n; i > 0; --i) invfact[i-1] = mul(invfact[i], i);
	for(int i = 1; i <= n; ++i) inv[i] = mul(invfact[i], fact[i-1]);
}
int binom(int n, int m){ return (m < 0 || m > n) ? 0 : mul(fact[n], mul(invfact[m], invfact[n-m])); }
const double pi = acos(-1);
inline void chmax(int &a, int b){ (b>a) ? (a=b) : 0; }
inline void chmin(int &a, int b){ (b<a) ? (a=b) : 0; }

int n, m;
string s[111];
bool done[111][111];
bool ok = 1;
bool dfs(int x, int y);
bool check(int x, int y){
	if((s[x][y] != '?') + (s[x][y+1] != '?') + (s[x+1][y] != '?') + (s[x+1][y+1] != '?') >= 3){
		if(s[x][y] != s[x][y+1] && s[x][y] == s[x+1][y+1] && s[x+1][y] == s[x][y+1]) return 0;
		//cout << "check " << x << " " << y << "\n";
		if(s[x][y] == s[x+1][y+1]){
			if(s[x+1][y] == '?'){
				if(s[x][y+1] == s[x][y]) return 1;
				else {
					s[x+1][y] = s[x][y];
					return dfs(x+1, y);
				}
			} else {
				if(s[x+1][y] == s[x][y]) return 1;
				else {
					s[x][y+1] = s[x][y];
					return dfs(x, y+1);
				}
			}
		}
		if(s[x][y+1] == s[x+1][y]){
			//cout << " ???\n";
			if(s[x][y] == '?'){
				if(s[x+1][y+1] == s[x+1][y]) return 1;
				else {
					s[x][y] = s[x+1][y];
					return dfs(x, y);
				}
			} else {
				if(s[x][y] == s[x+1][y]) return 1;
				else {
					s[x+1][y+1] = s[x+1][y];
					return dfs(x+1, y+1);
				}
			}
		}
	}
	return 1;
}
bool dfs(int x, int y){
	if(done[x][y]) return 1;
	done[x][y] = 1;
	if(x+1 < n && y+1 < m) if(!check(x, y)) return 0;
	if(x && y+1 < m) if(!check(x-1, y)) return 0;
	if(x+1 < n && y) if(!check(x, y-1)) return 0;
	if(x && y) if(!check(x-1, y-1)) return 0;
	return 1;
}

mt19937 rng(58);
inline int myrand(int l, int r){ return (int)(rng() % (r-l+1)) + l; }
string ans[111];

bool isok(int x, int y){
	return (x <= 0) || (y <= 0) || (x >= n) || (y >= m) || (ans[x][y] == '?' || ans[x][y-1] == '?' || ans[x-1][y] == '?' || ans[x-1][y-1] == '?' || ans[x][y] == ans[x][y-1] || ans[x][y] != ans[x-1][y-1] || ans[x][y-1] != ans[x-1][y]);
}

bool search(int x, int y){
	if(y >= m) ++x, y = 0;
	if(x >= n) return 1;
	auto nxt = [&](){
		if(isok(x, y) && isok(x+1, y) && isok(x, y+1) && isok(x+1, y+1) && search(x, y+1)) return 1;
		return 0;
	};
	if(s[x][y] != '?'){
		return nxt();
	} else {
		ans[x][y] = 'B';
		if(nxt()) return 1;
		ans[x][y] ^= ('W' ^ 'B');
		if(nxt()) return 1;
		ans[x][y] = '?';
		return 0;
	}
}

void solve(){
	cin >> n >> m;
	rep(i, n) cin >> s[i];
	rep(i, n) rep(j, m) done[i][j] = 0;
	ok = 1;
	rep(i, n) rep(j, m) if(s[i][j] != '?' && !done[i][j]) ok &= dfs(i, j);

	//cout << ": \n";
	//rep(i, n) cout << s[i] << "\n";

	if(!ok) cout << "NO\n";
	else {
		cout << "YES\n";
		rep(i, n) ans[i] = s[i];
		search(0, 0);
		rep(i, n) cout << ans[i] << "\n";
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int T;
	cin >> T;
	while(T--) solve();

	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3584kb

input:

3
2 2
??
??
3 3
BW?
W?B
?BW
3 3
BW?
W?W
?W?

output:

YES
BB
BB
NO
YES
BWB
WWW
BWB

result:

ok ok (3 test cases)

Test #2:

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

input:

10000
9 2
BB
BW
WW
WW
?W
?B
B?
W?
BB
6 2
??
?B
B?
BW
WW
??
10 7
WBBBW??
???BWWW
???BWWB
??WWBW?
BBWBBWB
WWB?WW?
BWBW???
WWWWBBW
BBWBB?W
B?W?W?B
4 7
??WBWWB
?BBWWWB
?W?BBB?
BBBWBBB
10 1
B
W
?
B
B
W
W
W
B
?
10 4
??WW
W?W?
WWW?
???W
?W??
?W?W
W?W?
?W?W
???W
???W
8 3
WBW
W??
???
???
W?W
W?W
???
?W?
4 1
...

output:

YES
BB
BW
WW
WW
BW
BB
BB
WB
BB
YES
BB
BB
BB
BW
WW
BB
NO
NO
YES
B
W
B
B
B
W
W
W
B
B
YES
BBWW
WBWB
WWWB
BBWW
BWWB
BWWW
WWWB
BWWW
BBBW
BBBW
YES
WBW
WBB
BBB
BBB
WBW
WBW
BBB
BWB
YES
W
B
B
B
YES
BBBB
WBBB
YES
BBBBBB
BBWBWB
YES
WBWBB
YES
BWBBBB
WWBBBB
BBBWBB
WBWWBW
YES
B
YES
BWB
BBB
WBB
BBB
WWB
BBB
BBW
BBB...

result:

ok ok (10000 test cases)

Test #3:

score: 0
Accepted
time: 19ms
memory: 3596kb

input:

10000
9 6
?B?W?W
WWBBWB
?WB?BW
B?W?W?
WW??W?
B???BW
?W?WW?
W?B?B?
?W?BB?
10 1
W
?
?
?
?
?
?
?
B
W
9 4
????
????
W???
?W?B
??WW
?BW?
WW?W
??W?
??W?
3 2
?W
?B
BB
2 7
?W?BWWB
??W???W
9 9
?BW?WWW?W
BW?WBBWWW
W?W????WW
W??WW??WW
W?BWB?B?W
??BB?WWWW
W???WBW?W
WWW???WWW
B?WWWWWW?
8 10
W??BWWW??B
?BWBWBW?BW...

output:

NO
YES
W
B
B
B
B
B
B
B
B
W
YES
BBBB
BBBB
WBBB
WWBB
BWWW
BBWB
WWWW
BBWB
BBWB
YES
BW
BB
BB
YES
BWBBWWB
BWWBBWW
NO
NO
YES
WWB
BWB
BBB
BBW
WWW
YES
BWBWWWBBB
BBBBBWBBB
WBBBBBBBW
WWWWBBBBB
BWBBBWBBW
BWBBWWBWW
BWBBBBBWB
YES
WBWBBWB
BBBBWWB
BWBWWWW
BWWWWBB
BBBBWWB
WBBBWBB
WWWBWWB
WWWWWWB
BWWBBWW
YES
WB
BB
B...

result:

ok ok (10000 test cases)

Test #4:

score: 0
Accepted
time: 19ms
memory: 3688kb

input:

10000
7 7
?B??BBW
????BB?
WBBB??B
WW?B???
?B??BBB
BBWB??B
B???BB?
10 6
W?WW??
W??W??
?WWWW?
?WW?WW
WW??W?
W?????
W?WW??
WW???W
WWW??W
?W??W?
2 6
?B??W?
B???BB
1 8
??BWB?W?
5 2
WB
W?
B?
BB
?W
7 5
W????
?WW??
???W?
WWWW?
W?W?W
?W?B?
W?WWB
8 5
B?WBW
B??WW
WWW?B
WBBWB
BW?WW
B?W?B
??WWB
BBW?B
10 4
WWWW
?...

output:

YES
BBBBBBW
BBBBBBB
WBBBBBB
WWBBBBB
BBBBBBB
BBWBBBB
BBBBBBB
YES
WBWWBB
WBBWBB
WWWWWB
BWWBWW
WWBBWB
WBBBBB
WBWWBB
WWWBBW
WWWBBW
BWBBWW
YES
BBBBWB
BBBBBB
YES
BBBWBBWB
YES
WB
WB
BB
BB
BW
YES
WBBBB
WWWBB
BBWWB
WWWWB
WBWWW
WWWBB
WBWWB
NO
YES
WWWW
BBBB
WBBB
WBBB
WWWB
BWWW
WWBB
WBBB
WBWW
BBWB
YES
BBBBBB
BB...

result:

ok ok (10000 test cases)

Test #5:

score: 0
Accepted
time: 15ms
memory: 3620kb

input:

10000
1 1
?
7 9
W?WB????B
?WB??B??W
BBB?W?WB?
WWW??WWW?
WW?B??W?W
?BWW??WWW
B?WW?W?WB
3 7
??BBBB?
BW?WW??
B??B?BW
1 6
?B?WWB
7 1
W
W
W
B
?
W
?
8 8
WW??W?B?
WWW?????
BB??WWWW
?W???WBW
BBW???WB
BWBWBWW?
?W?WW??B
BB?????W
10 8
WWW?W?BW
WB?W?WBW
WW?W?WBW
WWWW?WW?
WBWB?B?W
BW?BW??B
??WWBWWB
W?BW?BWW
W?W?...

output:

YES
B
YES
WWWBBBBBB
BWBBBBBBW
BBBBWBWBB
WWWBWWWWB
WWWBBBWWW
BBWWBBWWW
BBWWBWWWB
YES
BBBBBBB
BWBWWBB
BBBBBBW
YES
BBBWWB
YES
W
W
W
B
B
W
B
NO
NO
YES
WBBBBBB
NO
YES
WBB
BBB
BBB
BBB
BBB
BBB
BBB
NO
YES
BBB
BWB
WWB
BBB
BBW
BBW
BBB
BBB
BBB
BWB
YES
WW
BB
BB
BW
BB
BB
BB
NO
YES
BB
BB
BB
BB
BB
BB
BB
BB
NO
YES
...

result:

ok ok (10000 test cases)

Test #6:

score: 0
Accepted
time: 19ms
memory: 3684kb

input:

10000
9 1
W
B
?
B
W
W
?
W
B
1 10
W??????BWB
5 8
??W??WB?
?B?WWB?W
??????B?
BB??BBBB
WB??BBB?
6 2
?B
??
WB
?B
WW
W?
1 10
WW??BW?BW?
4 3
BW?
???
B?B
??W
10 10
WW?BBW?BW?
WW?BW?????
?WWBW?WB?W
???B?BBBBB
??BBBB?BBW
?WW??W?WBB
W??BB?WBBB
BBWBW?WBBW
?W????BWB?
??BW??WBWB
1 6
??B???
6 5
WBB?W
?WWWW
WWWW?
...

output:

YES
W
B
B
B
W
W
B
W
B
YES
WBBBBBBBWB
YES
BBWBWWBB
BBWWWBBW
BBBBBBBB
BBBBBBBB
WBBBBBBB
YES
BB
BB
WB
BB
WW
WB
YES
WWBBBWBBWB
YES
BWB
BBB
BBB
BBW
NO
YES
BBBBBB
NO
YES
B
B
B
B
B
B
B
B
B
YES
BWWWBWBBB
WWBBBBBWB
WWWWBBBBB
WBWWWWWWW
BBWBWBBWB
WBWWWBBWW
WWWWWWBWW
WWWWBWWWB
YES
WBBB
WWBW
WBBB
BBWB
BWWB
BBWB
...

result:

ok ok (10000 test cases)

Test #7:

score: 0
Accepted
time: 50ms
memory: 3684kb

input:

10000
10 10
?W?WW?W??W
?BWBW?BBWW
?BB?WWW?W?
W?B?WWWWWW
?BWW?WWW?W
BWWWWWWW?W
WBBWW??B??
W??WW?W??W
WWWW?WW?W?
?W?BWW?WW?
10 10
WB?WBBWWWB
?WWWW?WB??
?B?BWW?BW?
WBWBW??W?W
B?WB?WBWWB
WWBWBBWW??
??WBBWBWBW
WWB??WWBWB
B?BWWWWBWW
WW?WWWBWWB
10 10
??W????WW?
?WW?W???W?
??W??WW?W?
WW??WW?WW?
?W??WW?WW?
?...

output:

NO
NO
YES
BBWBBBBWWB
BWWBWBBBWB
BBWBWWWBWB
WWWBWWWWWB
BWBBWWBWWB
BWWBBWWWWW
BBBBBBWBBB
BBWWBWWWBB
BWWWBBBWBB
BWWWBBBBBW
NO
YES
BBBBWBBBWB
WWWBBBBBWB
BWBBWWBBBB
BBBBWWBBBW
BBBBBWBBWW
BBBBBBBBBB
BBWBWBBBBB
BBBBWWBWBB
BBBBBBBWBB
BBBWWBBBBB
YES
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBB...

result:

ok ok (10000 test cases)

Test #8:

score: 0
Accepted
time: 46ms
memory: 3712kb

input:

10000
10 10
?BBBBWBBB?
??W???WB??
BB?W???BB?
?B???BBB??
W??BB?WBBB
?B?B???W?W
?????BB???
?BW???B???
???BBB??BB
BWBBBBBBB?
10 10
BWW?WWB?BW
??B?WBBBWB
B??BB??BWB
BW?BWB???W
?WB?WWW?W?
B??B??W?BB
?WBB?WBB?B
BB??BBWBW?
WB??WBB?BW
?B???B?W??
10 10
??WWWB??BB
?WW???WBWW
???W??W?WW
?W?B?W?W??
WWB?WBB??W
B...

output:

YES
BBBBBWBBBB
BBWBBWWBBB
BBWWBBBBBB
BBBBBBBBBB
WBBBBBWBBB
BBBBBBWWBW
BBBBBBBBBB
BBWBBBBBBB
BBBBBBBBBB
BWBBBBBBBB
NO
YES
BBWWWBBBBB
BWWBBBWBWW
BBWWWBWBWW
BWWBWWWWWB
WWBBWBBBWW
BWWBWBBWWW
BWBBWWWWBW
WWWWWBWWWW
BBBWWBBWBW
WBBWWWBWBB
YES
BWBWWWBBWW
BWWWBWBBBB
WWBWWWWWBB
WWBBBWBWWW
BWWBBWWWWW
WWWWBBBBWB...

result:

ok ok (10000 test cases)

Test #9:

score: 0
Accepted
time: 24ms
memory: 3596kb

input:

10000
1 100
WWW?BWB?BB?BBW?BWBB?W??B?B?BWWBWB?WWB??BBBBB??BBBBB?BBBWBWWW?B?BBBWW??BBBW???B???W??W??BW?B?B?W??WB?
1 100
?WBW?WB?BBBB?BWBWB???WWB?BBB?BBW?B?B??W?B??BBW??WBBW???WW?BBBB?WWB?WBB???WBBB?BBW?W??BW?B??BBBBBBBWB
1 100
W?????BBB?BB?BB?????BWWWB?B???BB??????B??BWW???B??B?B???????BBB??B?BBB???B...

output:

YES
WWWBBWBBBBBBBWBBWBBBWBBBBBBBWWBWBBWWBBBBBBBBBBBBBBBBBBBWBWWWBBBBBBWWBBBBBWBBBBBBBWBBWBBBWBBBBBWBBWBB
YES
BWBWBWBBBBBBBBWBWBBBBWWBBBBBBBBWBBBBBBWBBBBBBWBBWBBWBBBWWBBBBBBWWBBWBBBBBWBBBBBBWBWBBBWBBBBBBBBBBBWB
YES
WBBBBBBBBBBBBBBBBBBBBWWWBBBBBBBBBBBBBBBBBBWWBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBWBBWBBWBB...

result:

ok ok (10000 test cases)

Test #10:

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

input:

10000
100 1
W
B
B
?
B
B
B
?
B
B
B
B
W
B
B
B
?
?
B
?
B
B
?
W
B
W
?
B
?
B
W
W
?
W
?
B
?
B
B
?
W
W
B
?
B
B
?
?
W
W
B
B
?
B
B
?
B
?
?
?
W
B
W
B
?
B
W
?
?
B
B
B
B
?
B
?
W
B
B
W
B
?
W
B
B
?
B
B
?
B
?
W
?
B
?
B
B
?
B
W
100 1
?
W
?
W
?
W
W
W
W
W
B
W
?
?
B
B
?
W
?
B
W
W
W
W
?
?
?
?
W
W
B
W
W
W
W
W
?
W
W
W
?
...

output:

YES
W
B
B
B
B
B
B
B
B
B
B
B
W
B
B
B
B
B
B
B
B
B
B
W
B
W
B
B
B
B
W
W
B
W
B
B
B
B
B
B
W
W
B
B
B
B
B
B
W
W
B
B
B
B
B
B
B
B
B
B
W
B
W
B
B
B
W
B
B
B
B
B
B
B
B
B
W
B
B
W
B
B
W
B
B
B
B
B
B
B
B
W
B
B
B
B
B
B
B
W
YES
B
W
B
W
B
W
W
W
W
W
B
W
B
B
B
B
B
W
B
B
W
W
W
W
B
B
B
B
W
W
B
W
W
W
W
W
B
W
W
W
B
W
B
W
B
B
...

result:

ok ok (10000 test cases)

Test #11:

score: 0
Accepted
time: 38ms
memory: 3672kb

input:

1000
100 10
WWWB?WWW?W
W????????W
WB?W??WW?W
WBB?WWW??B
?WWWW?WW?W
?WWWW?W?WB
?B??W?W???
WW?W?BWWW?
WW?B?W?W?W
????WW??W?
BWB??WWWW?
W??W??WW??
W?WBB??WWW
?WWBBWW?WW
?WBWW?B???
???WWW???W
??WW?WWW??
????W?BW?W
???W?W?W?W
?WW?WW?WB?
BW??WW?WW?
WB?WWWWW?W
??BWW??W?W
W??B?WWWW?
WWW?W??WWW
BBBW??W?W?
??...

output:

NO
NO
NO
NO
NO
NO
NO
YES
BBWBWWWBBW
WBWBWBWWWW
WBBBBBWBWW
WWBWWWWBBB
BBBWBWWWWB
WWWWBWWBWW
WWWWBWWBWW
WBWWWWWBWW
WWWBBWWWWW
BBWWBBBWBB
BBWBBBBBBB
BBWWBWBWWW
BBBBBBBBBW
BWWWBBWBWW
WWWWBWWWWB
WWWBBBWWWB
BWWBWWWWBB
WWWBWBWWBB
WWWBWWWWWW
WWWBWBBWBW
BBBBWBWWBB
BBBBWBWBBB
BBBBWBBBWW
WWWWWWBWWB
WBBBWBBBWW
...

result:

ok ok (1000 test cases)

Test #12:

score: -100
Time Limit Exceeded

input:

1000
10 100
BBWB??W??B?BWB?BBB??WWWW?B???WBB??WW???WWBW?B??W??BW?BWBBBW?BWBW?WBW?B?WWB??B?B?BBWWWBBBBW?BB???B?WB
??????WWWBWBBB??W??WW??BWBW??W??????WWWB?B??B?????W?B?????W??BBBBWBW??BWWWB???WBWB?BB?WW?B????W?WWB?
WB?BBBW?B??BB?WWW?B??WBB??W?BBW??BB??BB???BB??B??WB??W?B?B?WWWWW?BB??W?W?WBB??B?WWBBB?...

output:

NO
NO
NO
NO
YES
BBBBBBBBBBBWBBBBBBBBBBWBBBBBBBBBBBBBBBBBBBBBBBBBWWWWBBBBBBWBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBWWBBWBB
BBBBBBBBBBBBBBBBBBBBBWWBBBBWBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBWBBBBBWBBBBWBBBBBWWBW
BBWBBBBBBBBBBBBBBBBBBBWBBBBBBBBBBBBBBBBBBBBBBWBBBBBWBBBBBBBBBWWBBBBBWBBWBBBBBBBBBB...

result: