QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#408402 | #6398. Puzzle: Tapa | Rico64 | RE | 0ms | 3520kb | C++23 | 4.6kb | 2024-05-10 10:00:25 | 2024-05-10 10:00:26 |
Judging History
answer
#include <iostream>
#include <vector>
#include <map>
const int dx[] {-1, 0, 0, 1};
const int dy[] {0, -1, 1, 0};
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
bool dfs(int a, int L, vector<vi>& g, vi& btoa, vi& A, vi& B) {
if (A[a] != L) return 0;
A[a] = -1;
for (int b : g[a]) if (B[b] == L + 1) {
B[b] = 0;
if (btoa[b] == -1 || dfs(btoa[b], L + 1, g, btoa, A, B))
return btoa[b] = a, 1;
}
return 0;
}
int hopcroftKarp(vector<vi>& g, vi& btoa) {
int res = 0;
vi A(g.size()), B(btoa.size()), cur, next;
for (;;) {
fill(all(A), 0);
fill(all(B), 0);
/// Find the starting nodes for BFS (i.e. layer 0).
cur.clear();
for (int a : btoa) if(a != -1) A[a] = -1;
rep(a,0,sz(g)) if(A[a] == 0) cur.push_back(a);
/// Find all layers using bfs.
for (int lay = 1;; lay++) {
bool islast = 0;
next.clear();
for (int a : cur) for (int b : g[a]) {
if (btoa[b] == -1) {
B[b] = lay;
islast = 1;
}
else if (btoa[b] != a && !B[b]) {
B[b] = lay;
next.push_back(btoa[b]);
}
}
if (islast) break;
if (next.empty()) return res;
for (int a : next) A[a] = lay;
cur.swap(next);
}
/// Use DFS to scan for augmenting paths.
rep(a,0,sz(g))
res += dfs(a, 0, g, btoa, A, B);
}
}
int main() {
int xl, yl;
cin >> xl >> yl;
string input[xl * 2 - 1];
for (int y = 0; y < yl * 2 - 1; ++y) {
cin >> input[y];
}
bool req[xl][yl];
for (int x = 0; x < xl; ++x) {
for (int y = 0; y < yl; ++y) {
if ((x == 0 || x == xl - 1) && (y == 0 || y == yl - 1)) {
req[x][y] = input[x * 2][y * 2] == '2';
} else if (!(x == 0 || x == xl - 1) && !(y == 0 || y == yl - 1)) {
req[x][y] = input[x * 2][y * 2] == '7';
} else {
req[x][y] = input[x * 2][y * 2] == '4';
}
}
}
map<pair<int,int>, int> mpe;
for (int x = 0; x < xl; ++x) {
for (int y = 0; y < yl; ++y) {
if ((x + y) % 2 == 0) {
mpe[{x, y}] = mpe.size();
}
}
}
map<pair<int,int>, int> mpo;
for (int x = 0; x < xl; ++x) {
for (int y = 0; y < yl; ++y) {
if ((x + y) % 2 == 1) {
mpo[{x, y}] = mpo.size();
}
}
}
vector<vector<int>> ltr (mpe.size());
for (int x = 0; x < xl; ++x) {
for (int y = 0; y < yl; ++y) {
if ((x + y) % 2 == 1 || !req[x][y]) continue;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx >= xl || ny < 0 || ny >= yl || !req[nx][ny]) continue;
bool ise = x == 0 || x == xl - 1 || y == 0 || y == yl - 1;
bool nse = nx == 0 || nx == xl - 1 || ny == 0 || ny == yl - 1;
if ((ise && !nse) || (!ise && nse)) continue;
ltr[mpe[{x, y}]].push_back(mpo[{nx, ny}]);
}
}
}
vector<int> matches (mpo.size(), -1);
hopcroftKarp(ltr, matches);
for (int x = 0; x < xl; ++x) {
for (int y = 0; y < yl; ++y) {
if ((x + y) % 2 == 0 || !req[x][y]) continue;
if (matches[mpo[{x, y}]] == -1) {
cout << "NO" << endl;
return 0;
}
}
}
for (int x = 0; x < xl; ++x) {
for (int y = 0; y < yl; ++y) {
if ((x + y) % 2 == 1 || !req[x][y]) continue;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx >= xl || ny < 0 || ny >= yl || !req[nx][ny]) continue;
if (matches[mpo[{nx, ny}]] == mpe[{x, y}]) {
input[x * 2 + dx[i]][y * 2 + dy[i]] = '#';
}
}
}
}
cout << "YES" << endl;
for (int i = 0; i < yl * 2 - 1; ++i) {
for (char& c : input[i]) {
if (c == '#') {
c = '.';
} else if (c == '.') {
c = '#';
}
}
cout << input[i] << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3476kb
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: 3520kb
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: 3472kb
input:
2 2 2.2 ... 2.2
output:
YES 2.2 ### 2.2
result:
ok Correct.
Test #4:
score: -100
Runtime Error
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#...