QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#371763 | #6398. Puzzle: Tapa | comp_towels_cat# | WA | 1ms | 3672kb | C++17 | 3.3kb | 2024-03-30 15:46:41 | 2024-03-30 15:46:43 |
Judging History
answer
#include <bits/stdc++.h>
#define FOR(i, j, k) for(int i = j;i <= (k);++ i)
#define ROF(i, j, k) for(int i = j;i >= (k);-- i)
#define int long long
#define PII pair<int,int>
#define db double
#define x first
#define y second
#define sp(x) fixed << setprecision(x)
#define all(g) g.begin(), g.end()
#define M(x) x %= mod, x += mod, x %= mod
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define Yes cout << "Yes\n"
#define No cout << "No\n"
#define ANS cout << ans << '\n'
#define de(p) cout << #p << ' ' << p << '\n'
#define END(i, n) (i == n ? '\n' : ' ')
using namespace std;
const int N = 1e6 + 10, M = 1e5 + 10, mod = 1e9 + 7, INF = 0x3f3f3f3f;
int n, m, k;
char c[110][110];
int g[51][51];//(g[x][y] == 3 || g[x][y] == 5 || g[x][y] == 8) continue;
PII match[51][51];
int type[51][51];
bool st[51][51];
int dx[4] = {0,1,0,-1},dy[4] = {1,0,-1,0};
bool dfs(int a,int b)
{
FOR(i,0,3)
{
int x = dx[i] + a,y = dy[i] + b;
if (x < 1 || x > n || y > m || y < 1 || st[x][y] || g[x][y] != 7 ) continue;
st[x][y] = 1;
auto t = match[x][y];
if (t.first == 0 || dfs(t.x,t.y))
{
match[x][y] = {a,b};
return true;
}
}
return false;
}
bool dfs1(int a,int b)
{
FOR(i,0,3)
{
int x = dx[i] + a,y = dy[i] + b;
if (x < 1 || x > n || y > m || y < 1 || st[x][y] || g[x][y] == 3 || g[x][y] == 5 || g[x][y] == 8 || g[x][y] == 7) continue;
st[x][y] = 1;
auto t = match[x][y];
if (t.first == 0 || dfs1(t.x,t.y))
{
match[x][y] = {a,b};
return true;
}
}
return false;
}
void solve()
{
cin >> n >> m;
FOR(i,1,n * 2 - 1) cin >> c[i] + 1;
FOR(i,1,n * 2 - 1)
FOR(j,1,m * 2 - 1)
{
if (i & 1 && j & 1) g[i / 2 + 1][j / 2 + 1] = c[i][j] ^ 48;
}
int sum1 = 0,sum2 = 0,res1 = 0,res2 = 0;
FOR(x,1,n)
{
FOR(y,1,m)
{
if (g[x][y] == 3 || g[x][y] == 5 || g[x][y] == 8) continue;
memset(st,0,sizeof st);
if (g[x][y] == 7)
{
if (!dfs(x,y))
{
NO;
return;
}
}
else
{
if (!dfs1(x,y))
{
NO;
return;
}
}
}
}
FOR(i,1,n * 2 - 1)
FOR(j,1,m * 2 - 1)
{
if (i & 1 && j & 1) continue;
else c[i][j] = '#';
}
FOR(i,1,n)
FOR(j,1,m)
{
auto [x,y] = match[i][j];
if (match[i][j].first == 0) continue;
if (i == x)
{
c[i * 2 - 1][min(y,j) * 2 - 1 + 1] = '.';
}
else
{
c[min(x,i) * 2 - 1 + 1][j * 2 - 1] = '.';
}
}
YES;
FOR(i,1,n * 2 - 1)
FOR(j,1,m * 2 - 1)
{
cout << c[i][j];
if (j == m * 2 - 1) cout << '\n';
}
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T = 1;
// cin >> T;
while (T --)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3644kb
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: 1ms
memory: 3636kb
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: 3672kb
input:
2 2 2.2 ... 2.2
output:
YES 2.2 ### 2.2
result:
ok Correct.
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3640kb
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:
YES 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#...
result:
wrong answer Clue not satisfied at (1,27), non-consecutive shaded cells