QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#367740 | #5070. Check Pattern is Bad | bear0131 | TL | 76ms | 3712kb | C++14 | 4.1kb | 2024-03-26 12:52:44 | 2024-03-26 12:52:44 |
Judging History
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...