QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#288338#6398. Puzzle: TapaSlongodWA 1ms3588kbC++144.5kb2023-12-22 15:18:362023-12-22 15:18:36

Judging History

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

  • [2023-12-22 15:18:36]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3588kb
  • [2023-12-22 15:18:36]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
namespace Slongod{
const int N = 105 , M = 2e4+7;
int n , m , s , t , econt , no_man_counter , hu[M] , dep[M] , head[M] , edgeid[N][N];
struct EDGE{int to , nxt , w;}edge[M];
void add(int x , int y , int w , int &id)
{
    id = ++econt; edge[econt].to = y; edge[econt].w = w; edge[econt].nxt = head[x]; head[x] = econt;
    edge[++econt].to = x; edge[econt].w = 0; edge[econt].nxt = head[y]; head[y] = econt;
}
void add(int x , int y , int w)
{
    edge[++econt].to = y; edge[econt].w = w; edge[econt].nxt = head[x]; head[x] = econt;
    edge[++econt].to = x; edge[econt].w = 0; edge[econt].nxt = head[y]; head[y] = econt;
}
char x[N][N];

int left(int i , int j){i = (i + 1) / 2; j = (j + 1) / 2; return (i+j)&1;}
int id(int i , int j){i = (i + 1) / 2; j = (j + 1) / 2; return (i - 1) * m + j;}
bool isnum(int i , int j){return (i&1) and (j&1);}
bool hefa(int i , int j){return 1 <= i and i <= n*2-1 and 1 <= j and j <= m*2-1;}
int calc(int i , int j)
{
    if ((i == 1 or i == n*2-1) and (j == 1 or j == m*2-1)) {
        return 3;
    } else if (i == 1 or i == n*2-1 or j == 1 or j == m*2-1) {
        return 5;
    } else {
        return 8;
    }
}
void addedge(int x1 , int y1 , int x2 , int y2 , int &idd)
{
    if (calc(x1 , y1) == x[x1][y1] or calc(x2 , y2) == x[x2][y2]){return;}
    if (left(x1 , y1)){add(id(x1 , y1) , id(x2 , y2) , 1 , idd);}
    else{add(id(x2 , y2) , id(x1 , y1) , 1 , idd);}
}

bool bfs()
{
    for (int i = s; i <= t; i++){dep[i] = -1; hu[i] = head[i];}
    queue <int> q; q.push(s); dep[s] = 1;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = edge[i].nxt) {
            int v = edge[i].to , w = edge[i].w;
            if (dep[v] == -1 and w) {
                dep[v] = dep[u] + 1;
                q.push(v);
            }
        }
    } return dep[t] != -1;
}
int dfs(int u , int f)
{
    if (u == t){return f;} int used = 0;
    for (int i = hu[u]; i; i = edge[i].nxt) {
        int v = edge[i].to , w = edge[i].w;
        if (w and dep[v] == dep[u] + 1) {
            int tmp = dfs(v , min(f-used , w));
            edge[i].w -= tmp; edge[i^1].w += tmp; used += tmp;
            if (f == used){hu[u] = i; break;}
        }
    }
    if (!used){dep[u] = -1;} return used;
}
int dinic(){int re = 0;while(bfs()){re += dfs(s , 0x3f3f3f3);}return re;}

void main()
{
    cin >> n >> m; s = 0; t = id(n*2-1 , m*2-1) + 1;
    for (int i = 1; i <= n*2-1; i++) {
        for (int j = 1; j <= m*2-1; j++) {
            cin >> x[i][j];
        }
    }
    for (int i = 1; i <= n*2-1; i++) {
        for (int j = 1; j <= m*2-1; j++) {
            if (isnum(i , j)) {
                x[i][j] -= '0';
            }
        }
    }
    for (int i = 1; i <= n*2-1; i++) {
        for (int j = 1; j <= m*2-1; j++) {
            if (isnum(i , j)) {
                if (calc(i , j) == x[i][j]){continue;}
                no_man_counter++;
                if (left(i , j)){add(s , id(i,j) , 1);}
                else{add(id(i,j) , t , 1);}
            } else {
                if (!((i + j) & 1)){continue;}
                if (i & 1) {
                    if (j - 1 != 1 and j + 1 != m*2-1) {
                        addedge(i , j-1 , i , j+1 , edgeid[i][j]);
                    } else if (i == 1 or i == n*2-1) {
                        addedge(i , j-1 , i , j+1 , edgeid[i][j]);
                    }
                } else {
                    if (i - 1 != 1 and i + 1 != n*2-1) {
                        addedge(i-1 , j , i+1 , j , edgeid[i][j]);
                    } else if (j == 1 or j == m*2-1) {
                        addedge(i-1 , j , i+1 , j , edgeid[i][j]);
                    }
                }
            }
        }
    }
    if (!(no_man_counter&1) and dinic() == no_man_counter/2) {
        cout << "YES\n";
        for (int i = 1; i <= n*2-1; i++) {
            for (int j = 1; j <= m*2-1; j++) {
                if (isnum(i , j)) {
                    cout << char(x[i][j]+'0');
                } else {
                    if (edgeid[i][j] and edge[edgeid[i][j]].w == 0) {
                        cout << '.';
                    } else {
                        cout << '#';
                    }
                }
            } cout << '\n';
        }
    } else {
        cout << "NO\n";
    }
}
}int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.in" , "r" , stdin);
    #endif
    ios :: sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    return Slongod :: main(),0;
}

詳細信息

Test #1:

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

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

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

input:

2 2
2.2
...
2.2

output:

YES
2.2
###
2.2

result:

ok Correct.

Test #4:

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

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

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

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

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

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

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

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

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

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

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

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

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

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: -100
Wrong Answer
time: 1ms
memory: 3528kb

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:

NO

result:

wrong answer Jury has answer but participant has not.