QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#622517 | #6398. Puzzle: Tapa | Rosmontispes | WA | 1ms | 3856kb | C++20 | 4.7kb | 2024-10-08 22:14:34 | 2024-10-08 22:14:35 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int opr[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};
struct Hopcroft_Karp{
vector<vector<int>>adj;
vector<int>con,dst;
int n,m,k;
Hopcroft_Karp(int n,int m,int k = 1):n(n),m(m),k(k),adj(n),con(n * k + m),dst(n * k){}
void add_edge(int u,int v){
cerr<<u<<" "<<v<<"\n";
adj[u].push_back(v);
}
int dfs(int u){
for(auto &i:adj[u / k])
if(con[i] == -1||(dst[con[i]] == dst[u] + 1 && dfs(con[i]))){
con[i] = u;
con[u] = i;
return 1;
}
return 0;
}
int matching(){
int rt = 0;
fill(con.begin(),con.end(),-1);
while(1){
fill(dst.begin(),dst.end(),1e9);
vector<int>stk;
for(int i = 0;i < n * k;i ++)
if(con[i] == -1)
stk.emplace_back(i),dst[i] = 0;
for(int j = 0;j < stk.size();j ++)
for(auto &i:adj[stk[j] / k])
if(con[i] != -1 && dst[con[i]] == int(1e9))
stk.emplace_back(con[i]),dst[con[i]] = dst[stk[j]] + 1;
int fl = 0;
for(int i = 0;i < n * k;i ++)
if(con[i] == -1 && dfs(i))
fl ++;
if(!fl)
break;
rt += fl;
}
return rt;
}
vector<int>result(){
vector<int>rt(n * k);
for(int i = 0;i < n * k;i ++)
rt[i] = con[i];
return rt;
}
};
void solve()
{
int n,m;
cin>>n>>m;
int t1 = 0,t2 = 0;
vector<string>S(2 * n - 1);
vector<vector<int>>ar(n,vector<int>(m));
vector<vector<int>>idx(n,vector<int>(m));
vector<vector<int>>idd(n,vector<int>(m));
vector<pair<int,int>>xy(n * m);
int cnt = 0;
for(int i = 0;i < 2 * n - 1;i ++){
string s;
cin>>s;
cerr<<i<<"\n";
cerr<<s<<"\n";
S[i] = s;
if(i % 2 == 0){
for(int j = 0;j < 2 * m - 1;j += 2){
int res = s[j] - '0';
ar[i / 2][j / 2] = s[j] - '0';
if(res == 2 || res == 4 || res == 7)
idd[i / 2][j / 2] = 1,cnt ++;
else
idd[i / 2][j / 2] = 0;
}
}
}
for(int i = 0;i < 2 * n - 1;i ++)
for(int j = 0;j < 2 * m - 1;j ++){
if((i / 2 + j / 2) % 2 == 0 && S[i][j] != '.'){
xy[t1] = make_pair(i,j);
idx[i / 2][j / 2] = t1 ++;
}
}
for(int i = 0;i < 2 * n - 1;i ++)
for(int j = 0;j < 2 * m - 1;j ++){
if((i / 2 + j / 2) % 2 == 1 && S[i][j] != '.'){
idx[i / 2][j / 2] = t1 + t2;
xy[t1 + t2] = make_pair(i,j);
t2 ++;
}
}
if(cnt % 2 == 1){
cout<<"NO\n";
return;
}
Hopcroft_Karp hk(t1,t2);
for(int i = 0;i < n;i ++){
for(int j = 0;j < m;j ++){
if(i - 1 >= 0){
if(ar[i][j] != 4 && ar[i - 1][j] != 4){
if(idd[i][j] && idd[i - 1][j]){
if((i + j) % 2 == 0)
hk.add_edge(idx[i][j],idx[i - 1][j]);
else
hk.add_edge(idx[i - 1][j],idx[i][j]);
}
}
}
if(j - 1 >= 0){
if(idd[i][j - 1] && idd[i][j]){
if((i + j) % 2 == 0)
hk.add_edge(idx[i][j],idx[i][j - 1]);
else
hk.add_edge(idx[i][j - 1],idx[i][j]);
}
}
}
}
int ret = hk.matching();
if(ret != cnt / 2){
cout<<"NO\n";
return;
}
auto rsl = hk.result();
for(int i = 0;i < n * m;i ++)
cerr<<xy[i].first<<" "<<xy[i].second<<"\n";
for(int i = 0;i < t1;i ++){
if(rsl[i] == -1)
continue;
cerr<<i<<" "<<rsl[i]<<"\n";
auto [x,y] = xy[i];
auto [xx,yy] = xy[rsl[i]];
cerr<<x<<" "<<y<<" "<<xx<<" "<<yy<<"\n";
S[(x + xx) / 2][(y + yy) / 2] = '#';
}
cout<<"YES\n";
for(int i = 0;i < 2 * n - 1;i ++)
for(int j = 0;j < 2 * m - 1;j ++){
if(S[i][j] == '#')
S[i][j] = '.';
else if(S[i][j] == '.')
S[i][j] = '#';
}
for(int i = 0;i < 2 * n - 1;i ++)
cout<<S[i]<<"\n";
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
input:
3 3 2.4.3 ..... 5.8.5 ..... 3.5.3
output:
YES 2.4#3 ##### 5#8#5 ##### 3#5#3
result:
ok Correct.
Test #2:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
3 3 3.4.3 ..... 5.7.5 ..... 3.5.3
output:
NO
result:
ok Correct.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
2 2 2.2 ... 2.2
output:
YES 2.2 ### 2.2
result:
ok Correct.
Test #4:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
2 50 2.4.4.4.4.5.5.5.5.5.5.5.5.4.5.5.4.4.5.5.5.5.4.5.5.5.5.5.4.4.5.4.5.5.5.5.5.5.5.5.5.5.5.4.4.5.5.4.5.3 ................................................................................................... 2.5.5.4.4.5.5.5.4.4.5.5.5.4.5.5.5.5.5.5.5.5.4.4.4.5.5.5.5.5.5.4.4.4.5.5.5.5.5.5.5.4.4.5.5.5.5.4...
output:
NO
result:
ok Correct.
Test #5:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
2 50 2.4.4.5.5.5.5.5.5.5.5.5.4.4.5.5.5.5.4.4.5.5.4.4.5.5.5.4.5.4.4.4.5.4.4.5.4.4.5.5.5.5.4.4.5.5.5.5.5.2 ................................................................................................... 3.5.4.5.5.5.5.5.5.5.5.5.5.5.4.5.5.5.5.4.5.5.5.5.4.4.5.4.5.4.5.5.5.5.5.4.4.5.5.5.4.4.5.5.5.5.5.4...
output:
NO
result:
ok Correct.
Test #6:
score: 0
Accepted
time: 1ms
memory: 3568kb
input:
50 2 3.2 ... 5.4 ... 5.5 ... 4.4 ... 5.5 ... 5.5 ... 5.5 ... 5.5 ... 5.5 ... 5.5 ... 5.5 ... 5.4 ... 5.4 ... 5.5 ... 5.5 ... 5.5 ... 5.5 ... 5.5 ... 5.4 ... 5.4 ... 5.4 ... 5.4 ... 4.4 ... 5.5 ... 5.5 ... 4.4 ... 5.4 ... 5.4 ... 5.5 ... 4.5 ... 4.5 ... 5.5 ... 5.5 ... 5.5 ... 5.5 ... 5.5 ... 5.5 ......
output:
NO
result:
ok Correct.
Test #7:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
50 2 3.3 ... 5.4 ... 5.4 ... 5.4 ... 5.4 ... 5.5 ... 4.4 ... 4.4 ... 5.5 ... 4.4 ... 5.5 ... 5.5 ... 5.5 ... 5.5 ... 4.5 ... 5.5 ... 5.5 ... 5.4 ... 5.4 ... 5.5 ... 5.4 ... 5.5 ... 5.4 ... 5.4 ... 5.5 ... 5.5 ... 4.5 ... 4.5 ... 4.5 ... 4.5 ... 5.5 ... 5.4 ... 5.4 ... 5.5 ... 5.5 ... 4.4 ... 4.4 ......
output:
NO
result:
ok Correct.
Test #8:
score: -100
Wrong Answer
time: 0ms
memory: 3820kb
input:
3 50 3.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.4.4.5.5.5.5.4.4.5.5.5.5.5.5.5.5.4.4.5.5.4.4.5.4.4.5.3 ................................................................................................... 4.8.8.8.8.8.8.8.8.8.8.8.8.8.8.7.7.7.7.7.7.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.7.7.8...
output:
NO
result:
wrong answer Jury has answer but participant has not.