QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#253608#6398. Puzzle: TapasupepapupuWA 1ms3760kbC++173.5kb2023-11-17 09:59:182023-11-17 09:59:18

Judging History

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

  • [2023-11-17 09:59:18]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3760kb
  • [2023-11-17 09:59:18]
  • 提交

answer

#include <bits/stdc++.h>

#define x first
#define y second
#define el '\n'
#define debug(x) cout << #x << ": " << x << el
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 3e5 + 10, INF = 0x3f3f3f3f, mod = 998244353;

int n, m;
char g[110][110];
vector<int> G[110 * 110];
bool st[110 * 110];
int match[110 * 110];

int get(int x, int y) {
    return (x - 1) * (m * 2 - 1) + y - 1;
}

bool find(int u) {
    for (int v : G[u])
        if (!st[v]) {
            st[v] = 1;
            if (match[v] == 0 || find(match[v])) {
                match[v] = u;
                return 1;
            }
        }
    return 0;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n * 2 - 1; ++i) cin >> g[i] + 1;
    int tot = 0;
    for (int j = 1; j < m * 2 - 1; j += 2) {
        vector<int> is{1, n * 2 - 1};
        for (int i: is) {
            if (g[i][j] == '2' || g[i][j] == '4') {
                if (g[i][j + 2] == '2' || g[i][j + 2] == '4') {
                    if ((i + 1) / 2 + (j + 1) / 2 & 1) G[get(i, j)].emplace_back(get(i, j + 2));
                    else G[get(i, j + 2)].emplace_back(get(i, j));
                }
            }
       }
    }
    for (int i = 1; i < n * 2 - 1; i += 2) {
        vector<int> js{1, m * 2 - 1};
        for (int j: js) {
            if (g[i][j] == '2' || g[i][j] == '4') {
                if (g[i + 2][j] == '2' || g[i + 2][j] == '4') {
                    if ((i + 1) / 2 + (j + 1) / 2 & 1) G[get(i, j)].emplace_back(get(i + 2, j));
                    else G[get(i + 2, j)].emplace_back(get(i, j));
                }
            }
       }
    }
    for (int i = 1; i <= n * 2 - 1; i += 2) {
        for (int j = 1; j <= m * 2 - 1; j += 2) {
            if (g[i][j] == '2' || g[i][j] == '4' || g[i][j] == '7') 
                ++tot;
            if (g[i][j] == '7') {
                if (i + 2 <= n * 2 - 1 && g[i + 2][j] == '7') {
                    if ((i + 1) / 2 + (j + 1) / 2 & 1) G[get(i, j)].emplace_back(get(i + 2, j));
                    else G[get(i + 2, j)].emplace_back(get(i, j));
                }
                if (j + 2 <= m * 2 - 1 && g[i + 2][j] == '7') {
                    if ((i + 1) / 2 + (j + 1) / 2 & 1) G[get(i, j)].emplace_back(get(i, j + 2));
                    else G[get(i, j + 2)].emplace_back(get(i, j));
                }
            }
        }
    }
    int success = 0;
    for (int i = 1; i <= n * 2 - 1; i += 2) 
        for (int j = 1; j <= m * 2 - 1; j += 2) {
            int id = get(i, j);
            if (G[id].size() && (i + 1) / 2 + (j + 1) / 2 & 1 && !match[id]) {
                memset(st, 0, sizeof st);
                success += find(id);
            }
        }
    if (success * 2 != tot) return cout << "NO\n", 0;
    cout << "YES\n";
    for (int i = 1; i <= n * 2 - 1; i += 2) 
        for (int j = 1; j <= m * 2 - 1; j += 2) {
            int id = get(i, j);
            if (match[id]) {
                int x1 = id / (m * 2 - 1) + 1, y1 = id % (m * 2 - 1) + 1;
                int x2 = match[id] / (m * 2 - 1) + 1, y2 = match[id] % (m * 2 - 1) + 1;
                g[x1 + x2 >> 1][y1 + y2 >> 1] = '#';
            }
        }
    for (int i = 1; i <= n * 2 - 1; ++i) {
        for (int j = 1; j <= m * 2 - 1; ++j) {
            if (g[i][j] != '.' && g[i][j] != '#') cout << g[i][j];
            else cout << (char)('.' + '#' - g[i][j]);
        }
        cout << el;
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

2 2
2.2
...
2.2

output:

YES
2.2
###
2.2

result:

ok Correct.

Test #4:

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

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

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

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

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

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.