QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#243709#6398. Puzzle: Tapaucup-team1198#WA 1ms3628kbC++203.0kb2023-11-08 16:11:572023-11-08 16:11:58

Judging History

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

  • [2023-11-08 16:11:58]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3628kb
  • [2023-11-08 16:11:57]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()

char field[100][100];
char ans[100][100];
bool kek[100][100];

const int MAXN = 55 * 55;
vector<int> G[MAXN];
int used[MAXN];
int couple[MAXN];

bool khun(int v, int c) {
    if (used[v] == c)
        return false;
    used[v] = c;
    for (int u : G[v]) {
        if (couple[u] == -1) {
            couple[u] = v;
            return true;
        }
    }
    for (int u : G[v]) {
        if (khun(couple[u], c)) {
            couple[u] = v;
            return true;
        }
    }
    return false;
}


signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < 2 * n - 1; ++i) {
        for (int j = 0; j < 2 * m - 1; ++j) {
            cin >> field[i][j];
            ans[i][j] = field[i][j];
            if (ans[i][j] == '.')
                ans[i][j] = '#';
            else {
                if (ans[i][j] == '2' || ans[i][j] == '4' || ans[i][j] == '7')
                    kek[i / 2][j / 2] = true;
            }
        }
    }
    int left_cnt = 0;
    int right_cnt = 0;
    auto on_border = [&](int a, int b) {
        return a == 0 || a == n - 1 || b == 0 || b == m - 1;
    };
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (kek[i][j]) {
                if ((i + j) % 2 == 0)
                    ++left_cnt;
                else
                    ++right_cnt;
                if (i + 1 < n && kek[i + 1][j] && on_border(i, j) == on_border(i + 1, j)) {
                    if ((i + j) % 2 == 0)
                        G[i * m + j].emplace_back((i + 1) * m + j);
                    else
                        G[(i + 1) * m + j].emplace_back(i * m + j);
                }
                if (j + 1 < m && kek[i][j + 1] && on_border(i, j) == on_border(i, j + 1)) {
                    if ((i + j) % 2 == 0)
                        G[i * m + j].emplace_back(i * m + j + 1);
                    else
                        G[i * m + j + 1].emplace_back(i * m + j);
                }
            }
        }
    }
    if (left_cnt != right_cnt) {
        cout << "NO\n";
        return 0;
    }
    int cnt = 0;
    fill(used, used + n * m, -1);
    fill(couple, couple + n * m, -1);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if ((i + j) % 2 == 0)
                cnt += khun(i * m + j, i * m + j);
        }
    }
    if (cnt == left_cnt) {
        for (int i = 0; i < n * m; ++i) {
            if (couple[i] != -1) {
                int j = couple[i];
                int x1 = i / m, y1 = i % m;
                int x2 = j / m, y2 = j % m;
                ans[x1 + x2][y1 + y2] = '.';
            }
        }
        cout << "YES\n";
        for (int i = 0; i < 2 * n - 1; ++i) {
            for (int j = 0; j < 2 * m - 1; ++j)
                cout << ans[i][j];
            cout << '\n';
        }
    } else {
        cout << "NO\n";
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3492kb

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

input:

3 3
3.4.3
.....
5.7.5
.....
3.5.3

output:

NO

result:

ok Correct.

Test #3:

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

input:

2 2
2.2
...
2.2

output:

YES
2#2
.#.
2#2

result:

ok Correct.

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 3368kb

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