QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#216707#5135. Kiosk ConstructionMovingUp#WA 64ms35432kbC++142.6kb2023-10-15 21:26:402023-10-15 21:26:40

Judging History

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

  • [2023-10-15 21:26:40]
  • 评测
  • 测评结果:WA
  • 用时:64ms
  • 内存:35432kb
  • [2023-10-15 21:26:40]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1005;
const int inf = 1e9;

int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

vector<pair<int,int>> edge[Nmax][Nmax];
int dist[Nmax][Nmax], Dist[Nmax][Nmax];
int a[Nmax][Nmax];
int n, m;
bool ok[Nmax][Nmax];



void dfs(int x, int y)
{
    for(auto it : edge[x][y])
    {
        dist[it.first][it.second] = dist[x][y] + 1;
        dfs(it.first, it.second);
    }
}

bool valid(int x, int y)
{
    return (1<= x && x <= n && 1 <= y && y <= m);
}

void solve(int x, int y)
{
    int val = a[x][y];
    int i, j, k;

    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
        {
            edge[i][j].clear();
            dist[i][j] = -1;
        }

    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
        {
            if(i == x && j == y) continue;

            int curr_abs = inf, curr_abs2 = inf, pos_i = -1, pos_j = -1;
            for(k=0; k<4; ++k)
            {
                int ii = i + dx[k];
                int jj = j + dy[k];

                if(valid(ii, jj))
                {
                    if(abs(a[ii][jj] - val) < curr_abs || (abs(a[ii][jj] - val == curr_abs && abs(a[ii][jj] - a[i][j]) < curr_abs2)))
                    {
                        curr_abs = abs(a[ii][jj] - val);
                        curr_abs2 = abs(a[ii][jj] - a[i][j]);
                        pos_i = ii;
                        pos_j = jj;
                    }
                }
            }

            edge[pos_i][pos_j].push_back({i, j});
        }

    dist[x][y] = 0;
    dfs(x, y);

    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
        {
            Dist[i][j] = max(Dist[i][j], dist[i][j]);
            ok[i][j] &= (dist[i][j] != -1);
        }
}

int main()
{
   // freopen("input", "r", stdin);
    cin.tie(0); cin.sync_with_stdio(false);

    cin >> n >> m;

    int i, j;

    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
        {
            cin >> a[i][j];
            ok[i][j] = 1;
        }

    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
            solve(i, j);

    bool have_answer = 0;
    int x, y;

    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
            if(ok[i][j])
            {
                if(!have_answer || Dist[i][j] < Dist[x][y])
                {
                    have_answer = 1;
                    x = i, y = j;
                }
            }

    if(!have_answer)
        cout << "impossible\n";
    else cout << a[x][y] << ' ' << Dist[x][y] << '\n';

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 30364kb

input:

2 3
1 2 3
6 5 4

output:

2 2

result:

ok 

Test #2:

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

input:

3 3
1 4 8
7 5 2
3 9 6

output:

impossible

result:

ok 

Test #3:

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

input:

3 3
9 3 1
4 7 2
8 6 5

output:

4 3

result:

ok 

Test #4:

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

input:

2 2
1 2
3 4

output:

1 2

result:

ok 

Test #5:

score: 0
Accepted
time: 3ms
memory: 33032kb

input:

2 2
4 3
1 2

output:

4 2

result:

ok 

Test #6:

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

input:

2 3
3 5 2
6 1 4

output:

impossible

result:

ok 

Test #7:

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

input:

2 3
5 3 4
1 6 2

output:

6 2

result:

ok 

Test #8:

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

input:

3 2
2 4
6 3
1 5

output:

6 2

result:

ok 

Test #9:

score: 0
Accepted
time: 7ms
memory: 31320kb

input:

3 3
1 5 9
7 2 8
6 4 3

output:

impossible

result:

ok 

Test #10:

score: 0
Accepted
time: 4ms
memory: 33192kb

input:

3 3
8 3 9
5 6 2
1 4 7

output:

impossible

result:

ok 

Test #11:

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

input:

5 3
4 12 8
7 6 10
2 1 13
3 9 14
5 11 15

output:

impossible

result:

ok 

Test #12:

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

input:

5 5
24 23 3 10 1
6 7 9 18 5
25 2 20 11 8
4 13 12 14 15
17 21 22 19 16

output:

impossible

result:

ok 

Test #13:

score: 0
Accepted
time: 2ms
memory: 33216kb

input:

10 10
83 24 7 98 40 18 56 81 12 73
77 87 33 22 61 38 8 48 63 34
25 29 72 97 28 26 54 3 89 13
65 60 42 45 55 36 16 70 17 5
90 69 74 64 99 31 9 2 66 51
44 35 14 58 71 27 92 84 32 100
6 82 37 76 52 43 39 59 91 41
50 11 15 85 62 10 20 86 53 95
46 68 4 49 1 75 93 19 23 57
80 96 78 67 79 30 88 47 94 21

output:

impossible

result:

ok 

Test #14:

score: 0
Accepted
time: 4ms
memory: 30748kb

input:

20 10
86 175 137 160 149 72 135 64 2 131
134 83 66 148 141 1 171 90 178 57
108 152 179 136 47 67 142 124 121 59
146 41 126 89 114 118 196 112 125 19
26 180 50 107 96 188 128 14 94 88
156 7 49 76 91 117 56 104 161 127
105 195 184 40 24 139 3 190 106 80
116 21 34 12 87 97 130 140 103 98
192 81 157 194...

output:

impossible

result:

ok 

Test #15:

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

input:

2 40
59 36 73 43 16 15 2 49 51 21 30 79 60 78 48 19 4 45 77 65 3 63 22 11 57 58 54 76 27 70 25 12 62 69 29 1 50 35 14 17
71 56 13 66 75 26 6 68 37 72 46 38 53 8 41 24 32 31 33 80 23 64 5 52 20 9 40 61 34 10 39 47 67 74 42 18 7 55 28 44

output:

impossible

result:

ok 

Test #16:

score: 0
Accepted
time: 64ms
memory: 33340kb

input:

40 40
1545 1478 236 1013 790 988 319 1231 822 1598 1505 529 340 1441 224 681 1449 537 151 1087 966 552 938 101 676 136 807 1507 1079 328 1200 34 645 1127 316 518 357 726 121 1314
971 1266 564 954 468 627 1198 208 799 793 956 1206 70 343 406 221 142 408 1131 1533 504 1279 764 629 498 455 366 1407 991...

output:

impossible

result:

ok 

Test #17:

score: 0
Accepted
time: 56ms
memory: 30768kb

input:

40 40
1559 1253 109 396 934 203 833 1534 130 603 105 395 384 1521 713 647 1170 379 392 269 67 919 1447 429 784 688 106 885 763 853 621 680 1098 120 1486 1101 1099 852 748 1395
472 327 932 977 1451 65 670 460 673 838 1106 236 649 164 1407 1439 1068 1037 315 1326 70 143 474 1556 740 1390 237 938 1310 ...

output:

impossible

result:

ok 

Test #18:

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

input:

3 3
1 2 3
4 5 6
7 8 9

output:

1 4

result:

ok 

Test #19:

score: 0
Accepted
time: 29ms
memory: 33224kb

input:

40 31
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93
94 95 96 97 98 99 100 10...

output:

15 55

result:

ok 

Test #20:

score: 0
Accepted
time: 4ms
memory: 33068kb

input:

3 40
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

output:

20 22

result:

ok 

Test #21:

score: 0
Accepted
time: 3ms
memory: 30748kb

input:

40 3
1 2 3
4 5 6
7 8 9
10 11 12
13 14 15
16 17 18
19 20 21
22 23 24
25 26 27
28 29 30
31 32 33
34 35 36
37 38 39
40 41 42
43 44 45
46 47 48
49 50 51
52 53 54
55 56 57
58 59 60
61 62 63
64 65 66
67 68 69
70 71 72
73 74 75
76 77 78
79 80 81
82 83 84
85 86 87
88 89 90
91 92 93
94 95 96
97 98 99
100 101...

output:

1 41

result:

ok 

Test #22:

score: 0
Accepted
time: 50ms
memory: 30248kb

input:

40 40
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

output:

20 59

result:

ok 

Test #23:

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

input:

3 3
1 2 3
6 5 4
7 8 9

output:

5 2

result:

ok 

Test #24:

score: 0
Accepted
time: 12ms
memory: 30192kb

input:

27 27
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28
55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 ...

output:

365 26

result:

ok 

Test #25:

score: 0
Accepted
time: 9ms
memory: 33472kb

input:

21 10
1 2 3 4 5 6 7 8 9 10
20 19 18 17 16 15 14 13 12 11
21 22 23 24 25 26 27 28 29 30
40 39 38 37 36 35 34 33 32 31
41 42 43 44 45 46 47 48 49 50
60 59 58 57 56 55 54 53 52 51
61 62 63 64 65 66 67 68 69 70
80 79 78 77 76 75 74 73 72 71
81 82 83 84 85 86 87 88 89 90
100 99 98 97 96 95 94 93 92 91
10...

output:

105 15

result:

ok 

Test #26:

score: 0
Accepted
time: 16ms
memory: 31600kb

input:

40 21
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22
43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64
85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

output:

410 30

result:

ok 

Test #27:

score: 0
Accepted
time: 46ms
memory: 33552kb

input:

39 39
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40
79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

output:

761 38

result:

ok 

Test #28:

score: 0
Accepted
time: 48ms
memory: 35432kb

input:

40 40
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41
81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

output:

781 40

result:

ok 

Test #29:

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

input:

11 11
1 102 103 104 105 106 107 108 109 110 111
2 101 36 35 34 33 32 31 30 29 112
3 100 37 74 75 76 77 78 79 28 113
4 99 38 73 56 55 54 53 80 27 114
5 98 39 72 57 62 63 52 81 26 115
6 97 40 71 58 61 64 51 82 25 116
7 96 41 70 59 60 65 50 83 24 117
8 95 42 69 68 67 66 49 84 23 118
9 94 43 44 45 46 47...

output:

27 26

result:

FAIL Reported distance is not correct.