QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#408409#6398. Puzzle: TapaRico64WA 1ms3976kbC++234.9kb2024-05-10 10:13:082024-05-10 10:13:08

Judging History

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

  • [2024-05-10 10:13:08]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3976kb
  • [2024-05-10 10:13:08]
  • 提交

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 < xl * 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;
                if ((x == 0 && y > 0 && y < yl - 1 && dx[i] == 1) || (x == xl - 1 && y > 0 && y < yl - 1 && dx[i] == -1) ||
                    (y == 0 && x > 0 && x < xl - 1 && dy[i] == 1) || (y == yl - 1 && x > 0 && x < xl - 1 && dy[i] == -1) ||
                    (nx == 0 && ny > 0 && ny < yl - 1 && dx[i] == -1) || (nx == xl - 1 && ny > 0 && ny < yl - 1 && dx[i] == 1) ||
                    (ny == 0 && nx > 0 && nx < xl - 1 && dy[i] == -1) || (ny == yl - 1 && nx > 0 && nx < xl - 1 && dy[i] == 1)) 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 < xl * 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: 1ms
memory: 3696kb

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: 3504kb

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: 3580kb

input:

2 2
2.2
...
2.2

output:

YES
2.2
###
2.2

result:

ok Correct.

Test #4:

score: 0
Accepted
time: 0ms
memory: 3556kb

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: 1ms
memory: 3760kb

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: 0ms
memory: 3512kb

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: 0ms
memory: 3532kb

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: 0
Accepted
time: 0ms
memory: 3628kb

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:

YES
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#...

result:

ok Correct.

Test #9:

score: 0
Accepted
time: 1ms
memory: 3752kb

input:

3 50
2.4.4.4.5.4.4.4.4.4.4.5.5.4.4.5.5.4.4.5.5.5.4.4.5.5.5.4.4.5.5.4.4.4.4.5.5.5.5.5.5.4.4.5.5.5.5.4.4.3
...................................................................................................
5.7.7.8.7.7.7.7.8.8.8.8.7.7.8.7.7.8.8.8.8.7.7.8.8.8.7.7.8.7.7.8.8.8.8.7.7.8.8.7.7.8.8.8.7.7.8.8...

output:

YES
2.4#4.4#5#4.4#4.4#4.4#5#5#4.4#5#5#4.4#5#5#5#4.4#5#5#5#4.4#5#5#4.4#4.4#5#5#5#5#5#5#4.4#5#5#5#5#4.4#3
###################################################################################################
5#7.7#8#7.7#7.7#8#8#8#8#7.7#8#7.7#8#8#8#8#7.7#8#8#8#7.7#8#7.7#8#8#8#8#7.7#8#8#7.7#8#8#8#7.7#8#8#...

result:

ok Correct.

Test #10:

score: 0
Accepted
time: 1ms
memory: 3508kb

input:

50 3
3.5.3
.....
5.8.5
.....
5.8.5
.....
5.8.5
.....
5.8.5
.....
5.8.5
.....
5.8.4
.....
5.8.4
.....
4.8.5
.....
4.7.5
.....
5.7.5
.....
5.8.5
.....
5.8.4
.....
5.8.4
.....
5.8.5
.....
5.8.5
.....
5.8.5
.....
5.8.5
.....
5.8.5
.....
4.8.5
.....
4.7.5
.....
5.7.5
.....
5.8.5
.....
5.8.5
.....
5.8.5
....

output:

YES
3#5#3
#####
5#8#5
#####
5#8#5
#####
5#8#5
#####
5#8#5
#####
5#8#5
#####
5#8#4
####.
5#8#4
#####
4#8#5
.####
4#7#5
##.##
5#7#5
#####
5#8#5
#####
5#8#4
####.
5#8#4
#####
5#8#5
#####
5#8#5
#####
5#8#5
#####
5#8#5
#####
5#8#5
#####
4#8#5
.####
4#7#5
##.##
5#7#5
#####
5#8#5
#####
5#8#5
#####
5#8#5
##...

result:

ok Correct.

Test #11:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

50 3
2.4.3
.....
4.8.5
.....
4.8.5
.....
5.8.5
.....
4.7.4
.....
4.7.4
.....
4.8.5
.....
4.8.4
.....
5.8.4
.....
4.7.5
.....
4.7.5
.....
5.8.5
.....
5.8.5
.....
5.8.4
.....
5.8.4
.....
5.8.5
.....
5.8.5
.....
5.7.5
.....
5.7.5
.....
5.8.5
.....
5.8.5
.....
5.8.5
.....
4.8.5
.....
4.7.5
.....
4.7.4
....

output:

YES
2.4#3
#####
4#8#5
.####
4#8#5
#####
5#8#5
#####
4#7#4
.#.#.
4#7#4
#####
4#8#5
.####
4#8#4
####.
5#8#4
#####
4#7#5
.#.##
4#7#5
#####
5#8#5
#####
5#8#5
#####
5#8#4
####.
5#8#4
#####
5#8#5
#####
5#8#5
#####
5#7#5
##.##
5#7#5
#####
5#8#5
#####
5#8#5
#####
5#8#5
#####
4#8#5
.####
4#7#5
##.##
4#7#4
.#...

result:

ok Correct.

Test #12:

score: 0
Accepted
time: 0ms
memory: 3508kb

input:

10 10
2.4.4.4.5.5.4.4.5.2
...................
5.7.8.8.7.8.7.7.8.4
...................
4.7.8.8.7.8.8.8.8.5
...................
4.8.8.8.7.7.8.8.8.4
...................
5.8.7.7.7.7.8.8.7.4
...................
4.7.7.8.8.8.8.8.7.4
...................
4.8.7.8.8.7.7.7.8.4
...................
5.8.7.8.8.7.8....

output:

YES
2.4#4.4#5#5#4.4#5#2
##################.
5#7#8#8#7#8#7.7#8#4
##.#####.##########
4#7#8#8#7#8#8#8#8#5
.##################
4#8#8#8#7.7#8#8#8#4
##################.
5#8#7.7#7.7#8#8#7#4
################.##
4#7.7#8#8#8#8#8#7#4
.#################.
4#8#7#8#8#7#7.7#8#4
####.#####.########
5#8#7#8#8#7#8#8#...

result:

ok Correct.

Test #13:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

10 10
3.5.5.5.5.5.5.4.4.3
...................
5.7.7.8.8.7.8.7.7.4
...................
5.8.8.7.7.7.7.7.8.4
...................
5.8.7.7.8.8.8.7.7.5
...................
5.8.8.7.7.7.7.7.7.5
...................
4.7.7.8.8.7.8.8.7.4
...................
4.7.7.7.7.7.7.8.7.4
...................
5.8.7.8.7.7.7....

output:

NO

result:

ok Correct.

Test #14:

score: 0
Accepted
time: 1ms
memory: 3592kb

input:

10 10
2.4.5.4.4.5.5.5.5.3
...................
4.8.7.7.8.8.8.7.8.4
...................
4.8.7.8.7.8.8.7.8.4
...................
5.7.7.8.7.7.7.8.7.5
...................
5.7.8.8.8.8.8.8.7.5
...................
4.7.8.7.7.7.8.8.8.5
...................
4.7.7.7.8.7.7.8.8.5
...................
4.7.8.7.8.8.7....

output:

YES
2.4#5#4.4#5#5#5#5#3
###################
4#8#7.7#8#8#8#7#8#4
.#############.###.
4#8#7#8#7#8#8#7#8#4
####.###.##########
5#7#7#8#7#7.7#8#7#5
##.#############.##
5#7#8#8#8#8#8#8#7#5
###################
4#7#8#7.7#7#8#8#8#5
.#.#######.########
4#7#7.7#8#7#7#8#8#5
############.######
4#7#8#7#8#8#7#8#...

result:

ok Correct.

Test #15:

score: 0
Accepted
time: 1ms
memory: 3760kb

input:

10 10
2.4.4.4.5.5.4.4.5.3
...................
5.7.8.8.7.7.7.7.7.5
...................
5.7.7.7.8.7.7.8.7.5
...................
4.8.7.7.8.8.8.7.8.4
...................
4.8.8.8.7.8.8.7.8.4
...................
4.8.8.8.7.8.8.8.8.5
...................
4.8.7.8.7.7.7.8.8.4
...................
5.8.7.8.7.8.8....

output:

YES
2.4#4.4#5#5#4.4#5#3
###################
5#7#8#8#7.7#7.7#7#5
##.#############.##
5#7#7.7#8#7.7#8#7#5
###################
4#8#7.7#8#8#8#7#8#4
.#############.###.
4#8#8#8#7#8#8#7#8#4
########.##########
4#8#8#8#7#8#8#8#8#5
.##################
4#8#7#8#7#7.7#8#8#4
####.###.#########.
5#8#7#8#7#8#8#8#...

result:

ok Correct.

Test #16:

score: 0
Accepted
time: 1ms
memory: 3512kb

input:

10 10
3.5.4.4.5.5.4.4.5.3
...................
5.7.8.8.7.8.8.8.8.5
...................
5.7.8.8.7.7.7.8.8.5
...................
5.8.7.7.8.8.7.8.8.5
...................
5.8.8.8.8.8.7.8.8.4
...................
5.7.7.8.8.7.8.7.8.4
...................
5.7.8.8.8.7.7.7.8.5
...................
5.7.8.8.8.8.7....

output:

YES
3#5#4.4#5#5#4.4#5#3
###################
5#7#8#8#7#8#8#8#8#5
##.#####.##########
5#7#8#8#7#7.7#8#8#5
###################
5#8#7.7#8#8#7#8#8#5
############.######
5#8#8#8#8#8#7#8#8#4
##################.
5#7.7#8#8#7#8#7#8#4
##########.###.####
5#7#8#8#8#7#7#7#8#5
##.#########.######
5#7#8#8#8#8#7#8#...

result:

ok Correct.

Test #17:

score: 0
Accepted
time: 1ms
memory: 3564kb

input:

10 10
3.5.5.4.4.5.5.4.4.3
...................
5.7.7.7.7.8.8.7.7.5
...................
5.8.7.7.8.8.8.8.8.5
...................
5.7.8.8.8.7.7.8.8.4
...................
5.7.7.7.8.7.7.8.7.4
...................
5.8.8.8.7.7.8.8.7.5
...................
4.7.7.8.8.8.7.7.8.5
...................
4.8.8.8.7.7.8....

output:

YES
3#5#5#4.4#5#5#4.4#3
###################
5#7.7#7.7#8#8#7.7#5
###################
5#8#7.7#8#8#8#8#8#5
###################
5#7#8#8#8#7.7#8#8#4
##.###############.
5#7#7.7#8#7.7#8#7#4
################.##
5#8#8#8#7.7#8#8#7#5
###################
4#7.7#8#8#8#7.7#8#5
.##################
4#8#8#8#7.7#8#7#...

result:

ok Correct.

Test #18:

score: 0
Accepted
time: 1ms
memory: 3564kb

input:

10 10
2.4.4.5.4.4.4.4.4.2
...................
4.8.7.8.8.7.8.8.8.4
...................
4.8.7.8.7.7.7.7.7.4
...................
4.7.7.8.7.8.7.7.7.4
...................
5.8.7.8.7.7.8.8.8.4
...................
4.8.7.8.7.7.7.7.7.5
...................
4.8.7.7.8.8.7.7.7.5
...................
4.7.7.8.8.7.8....

output:

YES
2#4.4#5#4.4#4.4#4.2
.##################
4#8#7#8#8#7#8#8#8#4
####.#####.#######.
4#8#7#8#7#7#7.7#7#4
.#######.#######.##
4#7.7#8#7#8#7.7#7#4
##################.
5#8#7#8#7.7#8#8#8#4
####.##############
4#8#7#8#7.7#7.7#7#5
.###############.##
4#8#7.7#8#8#7.7#7#5
###################
4#7.7#8#8#7#8#8#...

result:

ok Correct.

Test #19:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

10 10
2.4.4.4.4.4.4.4.4.2
...................
4.8.8.7.7.7.7.8.8.5
...................
4.7.8.7.8.8.7.8.7.4
...................
4.7.8.7.7.8.7.7.7.4
...................
4.8.7.8.7.7.7.7.8.4
...................
4.8.7.8.7.7.7.7.7.4
...................
4.7.8.7.8.7.7.7.7.4
...................
4.7.7.7.7.7.7....

output:

YES
2.4#4.4#4.4#4.4#4.2
###################
4#8#8#7.7#7.7#8#8#5
.##################
4#7#8#7#8#8#7#8#7#4
##.###.#####.###.#.
4#7#8#7#7#8#7#7#7#4
.#######.#####.####
4#8#7#8#7#7.7#7#8#4
####.#############.
4#8#7#8#7.7#7.7#7#4
.###############.##
4#7#8#7#8#7.7#7#7#4
##.###.#######.###.
4#7#7#7#7#7.7#7#...

result:

ok Correct.

Test #20:

score: 0
Accepted
time: 1ms
memory: 3976kb

input:

50 50
3.5.5.5.5.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.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.3
...................................................................................................
5.8.8.8.8.7.7.8.8.8.8.8.7.7.8.8.8.7.7.7.8.8.8.8.8.8.8.8.8.8.8.7.8.8.8.7.7.8.8.8.8.8.8.8.8.7.8....

output:

YES
3#5#5#5#5#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#5#5#5#5#5#5#5#5#5#5#5#5#5#5#5#5#3
###################################################################################################
5#8#8#8#8#7.7#8#8#8#8#8#7.7#8#8#8#7#7.7#8#8#8#8#8#8#8#8#8#8#8#7#8#8#8#7.7#8#8#8#8#8#8#8#8#7#8#7....

result:

ok Correct.

Test #21:

score: -100
Wrong Answer
time: 0ms
memory: 3820kb

input:

50 50
3.5.5.5.4.4.5.5.5.5.5.5.5.5.5.5.5.5.4.4.5.4.4.4.4.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.3
...................................................................................................
4.8.8.8.8.8.8.7.7.8.8.8.8.8.8.8.8.8.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.8.8.8....

output:

YES
3#5#5#5#4.4#5#5#5#5#5#5#5#5#5#5#5#5#4.4#5#4.4#4.4#5#5#5#5#5#5#5#5#5#5#5#5#5#5#5#5#5#5#5#5#5#5#5#5#3
###################################################################################################
4#8#8#8#8#8#8#7.7#8#8#8#8#8#8#8#8#8#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#8#8#8#8#...

result:

wrong answer Clue not satisfied at (71,47)