oj.uz

Submission #769521

# Submission time Handle Problem Language Result Execution time Memory
769521 2023-06-29T17:49:07 Z danikoynov Maze (JOI23_ho_t3) C++14
62 / 100
 1365 ms 905432 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 6e6 + 10, block = sqrt(maxn) + 10;

struct cell
{
    int x, y;

    cell(int _x = 0, int _y = 0)
    {
        x = _x;
        y = _y;
    }

    cell add(const cell &r) const
    {
        cell d;
        d.x = x + r.x;
        d.y = y + r.y;
        return d;
    }
};

cell neib[4] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

int n, m, h;

vector < int > a[block], tr[block], tl[block];
vector < int > tu[block], td[block];
vector < int > ver_idx[block];

vector < pair < int, bool > > adj[3 * maxn];

int stx, sty, enx, eny;

int nxt;

int visit[3 * maxn], dist[3 * maxn];

void add_edges_row(int row, int i, int j, int ver)
{
    if (j - i + 1 == 2 * h - 1)
    {
        adj[ver].push_back({tr[row][i], 1});
        adj[ver].push_back({tl[row][j], 1});
    }
    else
    {
        if (i == 1)
            adj[ver].push_back({tl[row][j], 1});
        else
        {
            int to = i;
            if (i % (2 * h - 1) != 0)
                to = 2 * h - 1 - i % (2 * h - 1) + i;
            if (to >= j)
                adj[ver].push_back({tr[row][i], 1});
            else
            {
                adj[ver].push_back({tr[row][i], 1});
                adj[ver].push_back({tl[row][j], 1});
            }
        }
    }
}

void add_edges_col(int col, int i, int j, int ver)
{
    if (j - i + 1 == 2 * h - 1)
    {
        adj[ver].push_back({td[i][col], 1});
        adj[ver].push_back({tl[j][col], 1});
    }
    else
    {
        if (i == 1)
            adj[ver].push_back({td[i][col], 1});
        else
        {
            int to = i;
            if (i % (2 * h - 1) != 0)
                to = 2 * h - 1 - i % (2 * h - 1) + i;
            if (to >= j)
                adj[ver].push_back({tl[j][col], 1});
            else
            {
                adj[ver].push_back({td[i][col], 1});
                adj[ver].push_back({tl[j][col], 1});
            }
        }
    }
}

void solve()
{
    cin >> n >> m >> h;
    cin >> stx >> sty;
    cin >> enx >> eny;
    for (int i = 1; i <= n; i ++)
    {
        a[i].resize(m + 2);
        tl[i].resize(m + 2);
        tr[i].resize(m + 2);
        td[i].resize(m + 2);
        tu[i].resize(m + 2);
        ver_idx[i].resize(m + 2);


        for (int j = 1; j <= m; j ++)
        {
            char c;
            cin >> c;
            if (c == '.')
                a[i][j] = 0;
            else
                a[i][j] = 1;
        }
    }

    int cnt = 0;
    nxt = n * m;
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= m; j ++)
        {
            ver_idx[i][j] = ++ cnt;
        }
    }

    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= m; j ++)
        {
            tr[i][j] = ++ nxt;
            tl[i][j] = ++ nxt;
        }
        for (int j = 1; j <= m; j ++)
        {
            if (j % (2 * h - 1) != 0 && j != m)
                adj[tr[i][j]].push_back({tr[i][j + 1], 0});
            adj[tr[i][j]].push_back({ver_idx[i][j], 0});

            if ((j - 1) % (2 * h - 1) != 0)
                adj[tl[i][j]].push_back({tl[i][j - 1], 0});
            adj[tl[i][j]].push_back({ver_idx[i][j], 0});
        }
    }

    for (int j = 1; j <= m; j ++)
    {
        for (int i = 1; i <= n; i ++)
        {
            tu[i][j] = ++ nxt;
            td[i][j] = ++ nxt;
        }

        for (int i = 1; i <= n; i ++)
        {
            if (i % (2 * h - 1) != 0 && i != n)
                adj[td[i][j]].push_back({td[i + 1][j], 0});
            adj[td[i][j]].push_back({ver_idx[i][j], 0});

            if ((i - 1) % (2 * h - 1) != 0)
                adj[tu[i][j]].push_back({tu[i - 1][j], 0});
            adj[tu[i][j]].push_back({ver_idx[i][j], 0});
        }
    }

    ///exit(0);
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        {
            cell cur(i, j);
            for (int d = 0; d < 4; d ++)
            {
                cell nb = cur.add(neib[d]);
                if (nb.x > 0 && nb.x <= n && nb.y > 0 && nb.y <= m)
                    if (a[nb.x][nb.y] == 0)
                    {
                        adj[ver_idx[cur.x][cur.y]].push_back({ver_idx[nb.x][nb.y], 0});
                    }
            }


            int st_row = max(1, i - h), en_row = min(n, i + h);
            int st_col = max(1, j - h), en_col = min(m, j + h);
            int fs_row = st_row, ds_row = en_row;
            if (fs_row == i - h)
                fs_row ++;
            if (ds_row == i + h)
                ds_row --;
            ///cout << i << " " << j << " range " << st_row << " " << en_row << endl;
            ///add_edges(col_root[j], 1, n, fs_row, ds_row, ver_idx[i][j], 1);

            /// up row
            bool f1 = false, f2 = false;
            if (st_row == i - h)
            {
                if (st_col == j - h)
                    st_col ++, f1 = true;
                if (en_col == j + h)
                    en_col --, f2 = true;
            }
            ///add_edges(row_root[st_row], 1, m, st_col, en_col, ver_idx[i][j], 1);
            add_edges_row(st_row, st_col, en_col, ver_idx[i][j]);
            if (st_row == i - h)
            {
                if (f1)
                    st_col --;
                if (f2)
                    en_col ++;
            }



            /// down row
            f1 = f2 = false;
            if (en_row == i + h)
            {
                if (st_col == j - h)
                    st_col ++, f1 = true;
                if (en_col == j + h)
                    en_col --, f2 = true;
            }
            ////cout << i << " " << j << " range " << st_col << " " << en_col << endl;
            ///add_edges(row_root[en_row], 1, m, st_col, en_col, ver_idx[i][j], 1);
            add_edges_row(en_row, st_col, en_col, ver_idx[i][j]);

            if (en_row == i + h)
            {
                if (f1)
                    st_col --;
                if (f2)
                    en_col ++;
            }


            /// left col
            f1 = f2 = false;
            if (st_col == j - h)
            {
                if (st_row == i - h)
                    st_row ++, f1 = true;
                if (en_row == i + h)
                    en_row --, f2 = true;
            }
            ///add_edges(col_root[st_col], 1, n, st_row, en_row, ver_idx[i][j], 1);
            add_edges_col(st_col, st_row, en_row, ver_idx[i][j]);
            if (st_col == j - h)
            {
                if (f1)
                    st_row --;
                if (f2)
                    en_row ++;
            }

            /// right col
            f1 = f2 = false;
            if (en_col == j + h)
            {
                if (st_row == i - h)
                    st_row ++, f1 = true;
                if (en_row == i + h)
                    en_row --, f2 = true;
            }
            ///cout << i << " " << j << " " << "range " << st_row << " " << en_row << " col " << en_col << endl;
            ///add_edges(col_root[en_col], 1, n, st_row, en_row, ver_idx[i][j], 1);
            add_edges_col(en_col, st_row, en_row, ver_idx[i][j]);
            if (en_col == j + h)
            {
                if (f1)
                    st_row --;
                if (f2)
                    en_row ++;
            }
            /**for (int row = st_row; row <= en_row; row ++)
            {
                if (row == i - h || row == i + h)
                {
                    st_col ++, en_col --;

                    add_edges(row_root[row], 1, m, st_col, en_col, ver_idx[i][j], 1);
                    st_col --, en_col ++;
                }
                else
                {
                    adj[ver_idx[cur.x][cur.y]].push_back({fict[row][cur.y], 1});
                }
            }*/

        }


    for (int i = 1; i <= nxt; i ++)
        dist[i] = 1e9;

    deque < int > dq;
    dq.push_back(ver_idx[stx][sty]);
    dist[ver_idx[stx][sty]] = 0;
    while(!dq.empty())
    {
        int cur = dq.front();
        dq.pop_front();
        if (cur == ver_idx[enx][eny])
        {
            cout << dist[cur] << endl;
            return;
        }
        for (pair < int, int > nb : adj[cur])
        {
            int u = nb.first;
            int w = nb.second;
            if (dist[u] > dist[cur] + w)
            {
                dist[u] = dist[cur] + w;
                if (w == 0)
                    dq.push_front(u);
                else
                    dq.push_back(u);
            }
        }
    }
    /**for (int i = 1; i <= n; i ++, cout << endl)
        for (int j = 1; j <= m; j ++)
            cout << dist[ver_idx[i][j]] << " ";*/

    int ans = dist[ver_idx[enx][eny]];
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        {
            if (abs(i - enx) <= h && abs(j - eny) <= h)
            {
                if (abs(i - enx) + abs(j - eny) != 2 * h)
                {
                    ans = min(ans, dist[ver_idx[i][j]] + 1);
                }
            }
        }
    cout << ans << endl;


}

int main()
{
    speed();
    solve();
    return 0;
}
/**
3 3 2
1 1
3 3
.#.
##.
...
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 423304 KB Output is correct
2 Correct 175 ms 423332 KB Output is correct
3 Correct 184 ms 423568 KB Output is correct
4 Correct 172 ms 423672 KB Output is correct
5 Correct 175 ms 423656 KB Output is correct
6 Correct 174 ms 423564 KB Output is correct
7 Correct 176 ms 423664 KB Output is correct
8 Correct 171 ms 423536 KB Output is correct
9 Correct 173 ms 423316 KB Output is correct
10 Correct 175 ms 423260 KB Output is correct
11 Correct 174 ms 423316 KB Output is correct
12 Correct 173 ms 423252 KB Output is correct
13 Correct 172 ms 423392 KB Output is correct
14 Correct 175 ms 423308 KB Output is correct
15 Correct 171 ms 423272 KB Output is correct
16 Correct 172 ms 423656 KB Output is correct
17 Correct 175 ms 423572 KB Output is correct
18 Correct 172 ms 423512 KB Output is correct
19 Correct 207 ms 438904 KB Output is correct
20 Correct 188 ms 434824 KB Output is correct
21 Correct 211 ms 441892 KB Output is correct
22 Correct 210 ms 441488 KB Output is correct
23 Correct 205 ms 438196 KB Output is correct
24 Correct 217 ms 441936 KB Output is correct
25 Correct 193 ms 438220 KB Output is correct
26 Correct 202 ms 441636 KB Output is correct
27 Correct 203 ms 441392 KB Output is correct
28 Correct 198 ms 438356 KB Output is correct
29 Correct 272 ms 462344 KB Output is correct
30 Correct 203 ms 441460 KB Output is correct
31 Correct 239 ms 469976 KB Output is correct
32 Correct 281 ms 468412 KB Output is correct
33 Correct 282 ms 460720 KB Output is correct
34 Correct 247 ms 469724 KB Output is correct
35 Correct 236 ms 460460 KB Output is correct
36 Correct 271 ms 469320 KB Output is correct
37 Correct 267 ms 468512 KB Output is correct
38 Correct 235 ms 460860 KB Output is correct
39 Correct 1365 ms 813788 KB Output is correct
40 Correct 289 ms 475152 KB Output is correct
41 Correct 267 ms 480248 KB Output is correct
42 Correct 336 ms 482908 KB Output is correct
43 Correct 324 ms 492760 KB Output is correct
44 Correct 567 ms 652280 KB Output is correct
45 Correct 587 ms 641556 KB Output is correct
46 Correct 1185 ms 905432 KB Output is correct
47 Correct 1299 ms 875332 KB Output is correct
48 Correct 1280 ms 797304 KB Output is correct
49 Correct 849 ms 887428 KB Output is correct
50 Correct 720 ms 795280 KB Output is correct
51 Correct 1247 ms 882344 KB Output is correct
52 Correct 1186 ms 875588 KB Output is correct
53 Correct 1210 ms 797884 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 423272 KB Output is correct
2 Correct 185 ms 423364 KB Output is correct
3 Correct 184 ms 423316 KB Output is correct
4 Correct 193 ms 423240 KB Output is correct
5 Correct 199 ms 423524 KB Output is correct
6 Correct 200 ms 423348 KB Output is correct
7 Correct 183 ms 423368 KB Output is correct
8 Correct 197 ms 423364 KB Output is correct
9 Correct 184 ms 423564 KB Output is correct
10 Correct 190 ms 423664 KB Output is correct
11 Correct 209 ms 423624 KB Output is correct
12 Correct 188 ms 423596 KB Output is correct
13 Correct 209 ms 423500 KB Output is correct
14 Correct 191 ms 423512 KB Output is correct
15 Correct 184 ms 423620 KB Output is correct
16 Correct 185 ms 423600 KB Output is correct
17 Correct 184 ms 423608 KB Output is correct
18 Correct 183 ms 423360 KB Output is correct
19 Correct 193 ms 423516 KB Output is correct
20 Correct 185 ms 423368 KB Output is correct
21 Correct 183 ms 423372 KB Output is correct
22 Correct 186 ms 423520 KB Output is correct
23 Correct 206 ms 423312 KB Output is correct
24 Correct 187 ms 423424 KB Output is correct
25 Correct 184 ms 423356 KB Output is correct
26 Correct 183 ms 423384 KB Output is correct
27 Correct 184 ms 423408 KB Output is correct
28 Correct 202 ms 423496 KB Output is correct
29 Correct 184 ms 423260 KB Output is correct
30 Correct 182 ms 423612 KB Output is correct
31 Correct 182 ms 423608 KB Output is correct
32 Correct 183 ms 423584 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 423240 KB Output is correct
2 Correct 188 ms 423340 KB Output is correct
3 Correct 181 ms 423368 KB Output is correct
4 Correct 186 ms 423352 KB Output is correct
5 Correct 183 ms 423368 KB Output is correct
6 Correct 180 ms 423356 KB Output is correct
7 Correct 184 ms 423628 KB Output is correct
8 Correct 183 ms 423656 KB Output is correct
9 Correct 183 ms 423488 KB Output is correct
10 Correct 184 ms 423492 KB Output is correct
11 Correct 192 ms 423452 KB Output is correct
12 Correct 188 ms 423672 KB Output is correct
13 Correct 182 ms 423360 KB Output is correct
14 Correct 184 ms 423456 KB Output is correct
15 Correct 182 ms 423284 KB Output is correct
16 Correct 182 ms 423520 KB Output is correct
17 Correct 182 ms 423420 KB Output is correct
18 Correct 181 ms 423316 KB Output is correct
19 Correct 184 ms 423368 KB Output is correct
20 Correct 183 ms 423324 KB Output is correct
21 Correct 184 ms 423500 KB Output is correct
22 Correct 182 ms 423568 KB Output is correct
23 Correct 195 ms 423604 KB Output is correct
24 Correct 183 ms 423864 KB Output is correct
25 Correct 205 ms 434572 KB Output is correct
26 Correct 222 ms 440504 KB Output is correct
27 Correct 212 ms 441956 KB Output is correct
28 Correct 215 ms 438232 KB Output is correct
29 Correct 216 ms 437840 KB Output is correct
30 Correct 212 ms 436340 KB Output is correct
31 Correct 264 ms 438724 KB Output is correct
32 Correct 215 ms 441788 KB Output is correct
33 Correct 215 ms 441388 KB Output is correct
34 Correct 277 ms 460408 KB Output is correct
35 Correct 297 ms 470168 KB Output is correct
36 Correct 271 ms 460664 KB Output is correct
37 Correct 267 ms 459764 KB Output is correct
38 Correct 257 ms 455928 KB Output is correct
39 Correct 465 ms 558560 KB Output is correct
40 Correct 992 ms 792976 KB Output is correct
41 Correct 1126 ms 905308 KB Output is correct
42 Correct 1085 ms 795852 KB Output is correct
43 Correct 1052 ms 787228 KB Output is correct
44 Correct 932 ms 748196 KB Output is correct
45 Correct 1165 ms 845852 KB Output is correct
46 Correct 1116 ms 845304 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 423272 KB Output is correct
2 Correct 185 ms 423364 KB Output is correct
3 Correct 184 ms 423316 KB Output is correct
4 Correct 193 ms 423240 KB Output is correct
5 Correct 199 ms 423524 KB Output is correct
6 Correct 200 ms 423348 KB Output is correct
7 Correct 183 ms 423368 KB Output is correct
8 Correct 197 ms 423364 KB Output is correct
9 Correct 184 ms 423564 KB Output is correct
10 Correct 190 ms 423664 KB Output is correct
11 Correct 209 ms 423624 KB Output is correct
12 Correct 188 ms 423596 KB Output is correct
13 Correct 209 ms 423500 KB Output is correct
14 Correct 191 ms 423512 KB Output is correct
15 Correct 184 ms 423620 KB Output is correct
16 Correct 185 ms 423600 KB Output is correct
17 Correct 184 ms 423608 KB Output is correct
18 Correct 183 ms 423360 KB Output is correct
19 Correct 193 ms 423516 KB Output is correct
20 Correct 185 ms 423368 KB Output is correct
21 Correct 183 ms 423372 KB Output is correct
22 Correct 186 ms 423520 KB Output is correct
23 Correct 206 ms 423312 KB Output is correct
24 Correct 187 ms 423424 KB Output is correct
25 Correct 184 ms 423356 KB Output is correct
26 Correct 183 ms 423384 KB Output is correct
27 Correct 184 ms 423408 KB Output is correct
28 Correct 202 ms 423496 KB Output is correct
29 Correct 184 ms 423260 KB Output is correct
30 Correct 182 ms 423612 KB Output is correct
31 Correct 182 ms 423608 KB Output is correct
32 Correct 183 ms 423584 KB Output is correct
33 Correct 233 ms 438948 KB Output is correct
34 Correct 188 ms 423920 KB Output is correct
35 Correct 184 ms 424464 KB Output is correct
36 Correct 229 ms 434508 KB Output is correct
37 Correct 206 ms 434980 KB Output is correct
38 Correct 218 ms 440396 KB Output is correct
39 Correct 218 ms 441960 KB Output is correct
40 Correct 230 ms 441440 KB Output is correct
41 Correct 231 ms 438236 KB Output is correct
42 Correct 222 ms 438244 KB Output is correct
43 Correct 218 ms 437836 KB Output is correct
44 Correct 212 ms 436396 KB Output is correct
45 Correct 216 ms 441932 KB Output is correct
46 Correct 207 ms 438300 KB Output is correct
47 Correct 218 ms 438348 KB Output is correct
48 Correct 223 ms 438816 KB Output is correct
49 Correct 218 ms 438840 KB Output is correct
50 Correct 220 ms 438728 KB Output is correct
51 Correct 245 ms 438744 KB Output is correct
52 Correct 214 ms 441792 KB Output is correct
53 Correct 217 ms 441396 KB Output is correct
54 Correct 213 ms 438376 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 423272 KB Output is correct
2 Correct 185 ms 423364 KB Output is correct
3 Correct 184 ms 423316 KB Output is correct
4 Correct 193 ms 423240 KB Output is correct
5 Correct 199 ms 423524 KB Output is correct
6 Correct 200 ms 423348 KB Output is correct
7 Correct 183 ms 423368 KB Output is correct
8 Correct 197 ms 423364 KB Output is correct
9 Correct 184 ms 423564 KB Output is correct
10 Correct 190 ms 423664 KB Output is correct
11 Correct 209 ms 423624 KB Output is correct
12 Correct 188 ms 423596 KB Output is correct
13 Correct 209 ms 423500 KB Output is correct
14 Correct 191 ms 423512 KB Output is correct
15 Correct 184 ms 423620 KB Output is correct
16 Correct 185 ms 423600 KB Output is correct
17 Correct 184 ms 423608 KB Output is correct
18 Correct 183 ms 423360 KB Output is correct
19 Correct 193 ms 423516 KB Output is correct
20 Correct 185 ms 423368 KB Output is correct
21 Correct 183 ms 423372 KB Output is correct
22 Correct 186 ms 423520 KB Output is correct
23 Correct 206 ms 423312 KB Output is correct
24 Correct 187 ms 423424 KB Output is correct
25 Correct 184 ms 423356 KB Output is correct
26 Correct 183 ms 423384 KB Output is correct
27 Correct 184 ms 423408 KB Output is correct
28 Correct 202 ms 423496 KB Output is correct
29 Correct 184 ms 423260 KB Output is correct
30 Correct 182 ms 423612 KB Output is correct
31 Correct 182 ms 423608 KB Output is correct
32 Correct 183 ms 423584 KB Output is correct
33 Correct 233 ms 438948 KB Output is correct
34 Correct 188 ms 423920 KB Output is correct
35 Correct 184 ms 424464 KB Output is correct
36 Correct 229 ms 434508 KB Output is correct
37 Correct 206 ms 434980 KB Output is correct
38 Correct 218 ms 440396 KB Output is correct
39 Correct 218 ms 441960 KB Output is correct
40 Correct 230 ms 441440 KB Output is correct
41 Correct 231 ms 438236 KB Output is correct
42 Correct 222 ms 438244 KB Output is correct
43 Correct 218 ms 437836 KB Output is correct
44 Correct 212 ms 436396 KB Output is correct
45 Correct 216 ms 441932 KB Output is correct
46 Correct 207 ms 438300 KB Output is correct
47 Correct 218 ms 438348 KB Output is correct
48 Correct 223 ms 438816 KB Output is correct
49 Correct 218 ms 438840 KB Output is correct
50 Correct 220 ms 438728 KB Output is correct
51 Correct 245 ms 438744 KB Output is correct
52 Correct 214 ms 441792 KB Output is correct
53 Correct 217 ms 441396 KB Output is correct
54 Correct 213 ms 438376 KB Output is correct
55 Correct 281 ms 462504 KB Output is correct
56 Correct 217 ms 441520 KB Output is correct
57 Correct 300 ms 460404 KB Output is correct
58 Incorrect 283 ms 462464 KB Output isn't correct
59 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 423304 KB Output is correct
2 Correct 175 ms 423332 KB Output is correct
3 Correct 184 ms 423568 KB Output is correct
4 Correct 172 ms 423672 KB Output is correct
5 Correct 175 ms 423656 KB Output is correct
6 Correct 174 ms 423564 KB Output is correct
7 Correct 176 ms 423664 KB Output is correct
8 Correct 171 ms 423536 KB Output is correct
9 Correct 173 ms 423316 KB Output is correct
10 Correct 175 ms 423260 KB Output is correct
11 Correct 174 ms 423316 KB Output is correct
12 Correct 173 ms 423252 KB Output is correct
13 Correct 172 ms 423392 KB Output is correct
14 Correct 175 ms 423308 KB Output is correct
15 Correct 171 ms 423272 KB Output is correct
16 Correct 172 ms 423656 KB Output is correct
17 Correct 175 ms 423572 KB Output is correct
18 Correct 172 ms 423512 KB Output is correct
19 Correct 207 ms 438904 KB Output is correct
20 Correct 188 ms 434824 KB Output is correct
21 Correct 211 ms 441892 KB Output is correct
22 Correct 210 ms 441488 KB Output is correct
23 Correct 205 ms 438196 KB Output is correct
24 Correct 217 ms 441936 KB Output is correct
25 Correct 193 ms 438220 KB Output is correct
26 Correct 202 ms 441636 KB Output is correct
27 Correct 203 ms 441392 KB Output is correct
28 Correct 198 ms 438356 KB Output is correct
29 Correct 272 ms 462344 KB Output is correct
30 Correct 203 ms 441460 KB Output is correct
31 Correct 239 ms 469976 KB Output is correct
32 Correct 281 ms 468412 KB Output is correct
33 Correct 282 ms 460720 KB Output is correct
34 Correct 247 ms 469724 KB Output is correct
35 Correct 236 ms 460460 KB Output is correct
36 Correct 271 ms 469320 KB Output is correct
37 Correct 267 ms 468512 KB Output is correct
38 Correct 235 ms 460860 KB Output is correct
39 Correct 1365 ms 813788 KB Output is correct
40 Correct 289 ms 475152 KB Output is correct
41 Correct 267 ms 480248 KB Output is correct
42 Correct 336 ms 482908 KB Output is correct
43 Correct 324 ms 492760 KB Output is correct
44 Correct 567 ms 652280 KB Output is correct
45 Correct 587 ms 641556 KB Output is correct
46 Correct 1185 ms 905432 KB Output is correct
47 Correct 1299 ms 875332 KB Output is correct
48 Correct 1280 ms 797304 KB Output is correct
49 Correct 849 ms 887428 KB Output is correct
50 Correct 720 ms 795280 KB Output is correct
51 Correct 1247 ms 882344 KB Output is correct
52 Correct 1186 ms 875588 KB Output is correct
53 Correct 1210 ms 797884 KB Output is correct
54 Correct 190 ms 423272 KB Output is correct
55 Correct 185 ms 423364 KB Output is correct
56 Correct 184 ms 423316 KB Output is correct
57 Correct 193 ms 423240 KB Output is correct
58 Correct 199 ms 423524 KB Output is correct
59 Correct 200 ms 423348 KB Output is correct
60 Correct 183 ms 423368 KB Output is correct
61 Correct 197 ms 423364 KB Output is correct
62 Correct 184 ms 423564 KB Output is correct
63 Correct 190 ms 423664 KB Output is correct
64 Correct 209 ms 423624 KB Output is correct
65 Correct 188 ms 423596 KB Output is correct
66 Correct 209 ms 423500 KB Output is correct
67 Correct 191 ms 423512 KB Output is correct
68 Correct 184 ms 423620 KB Output is correct
69 Correct 185 ms 423600 KB Output is correct
70 Correct 184 ms 423608 KB Output is correct
71 Correct 183 ms 423360 KB Output is correct
72 Correct 193 ms 423516 KB Output is correct
73 Correct 185 ms 423368 KB Output is correct
74 Correct 183 ms 423372 KB Output is correct
75 Correct 186 ms 423520 KB Output is correct
76 Correct 206 ms 423312 KB Output is correct
77 Correct 187 ms 423424 KB Output is correct
78 Correct 184 ms 423356 KB Output is correct
79 Correct 183 ms 423384 KB Output is correct
80 Correct 184 ms 423408 KB Output is correct
81 Correct 202 ms 423496 KB Output is correct
82 Correct 184 ms 423260 KB Output is correct
83 Correct 182 ms 423612 KB Output is correct
84 Correct 182 ms 423608 KB Output is correct
85 Correct 183 ms 423584 KB Output is correct
86 Correct 188 ms 423240 KB Output is correct
87 Correct 188 ms 423340 KB Output is correct
88 Correct 181 ms 423368 KB Output is correct
89 Correct 186 ms 423352 KB Output is correct
90 Correct 183 ms 423368 KB Output is correct
91 Correct 180 ms 423356 KB Output is correct
92 Correct 184 ms 423628 KB Output is correct
93 Correct 183 ms 423656 KB Output is correct
94 Correct 183 ms 423488 KB Output is correct
95 Correct 184 ms 423492 KB Output is correct
96 Correct 192 ms 423452 KB Output is correct
97 Correct 188 ms 423672 KB Output is correct
98 Correct 182 ms 423360 KB Output is correct
99 Correct 184 ms 423456 KB Output is correct
100 Correct 182 ms 423284 KB Output is correct
101 Correct 182 ms 423520 KB Output is correct
102 Correct 182 ms 423420 KB Output is correct
103 Correct 181 ms 423316 KB Output is correct
104 Correct 184 ms 423368 KB Output is correct
105 Correct 183 ms 423324 KB Output is correct
106 Correct 184 ms 423500 KB Output is correct
107 Correct 182 ms 423568 KB Output is correct
108 Correct 195 ms 423604 KB Output is correct
109 Correct 183 ms 423864 KB Output is correct
110 Correct 205 ms 434572 KB Output is correct
111 Correct 222 ms 440504 KB Output is correct
112 Correct 212 ms 441956 KB Output is correct
113 Correct 215 ms 438232 KB Output is correct
114 Correct 216 ms 437840 KB Output is correct
115 Correct 212 ms 436340 KB Output is correct
116 Correct 264 ms 438724 KB Output is correct
117 Correct 215 ms 441788 KB Output is correct
118 Correct 215 ms 441388 KB Output is correct
119 Correct 277 ms 460408 KB Output is correct
120 Correct 297 ms 470168 KB Output is correct
121 Correct 271 ms 460664 KB Output is correct
122 Correct 267 ms 459764 KB Output is correct
123 Correct 257 ms 455928 KB Output is correct
124 Correct 465 ms 558560 KB Output is correct
125 Correct 992 ms 792976 KB Output is correct
126 Correct 1126 ms 905308 KB Output is correct
127 Correct 1085 ms 795852 KB Output is correct
128 Correct 1052 ms 787228 KB Output is correct
129 Correct 932 ms 748196 KB Output is correct
130 Correct 1165 ms 845852 KB Output is correct
131 Correct 1116 ms 845304 KB Output is correct
132 Correct 233 ms 438948 KB Output is correct
133 Correct 188 ms 423920 KB Output is correct
134 Correct 184 ms 424464 KB Output is correct
135 Correct 229 ms 434508 KB Output is correct
136 Correct 206 ms 434980 KB Output is correct
137 Correct 218 ms 440396 KB Output is correct
138 Correct 218 ms 441960 KB Output is correct
139 Correct 230 ms 441440 KB Output is correct
140 Correct 231 ms 438236 KB Output is correct
141 Correct 222 ms 438244 KB Output is correct
142 Correct 218 ms 437836 KB Output is correct
143 Correct 212 ms 436396 KB Output is correct
144 Correct 216 ms 441932 KB Output is correct
145 Correct 207 ms 438300 KB Output is correct
146 Correct 218 ms 438348 KB Output is correct
147 Correct 223 ms 438816 KB Output is correct
148 Correct 218 ms 438840 KB Output is correct
149 Correct 220 ms 438728 KB Output is correct
150 Correct 245 ms 438744 KB Output is correct
151 Correct 214 ms 441792 KB Output is correct
152 Correct 217 ms 441396 KB Output is correct
153 Correct 213 ms 438376 KB Output is correct
154 Correct 281 ms 462504 KB Output is correct
155 Correct 217 ms 441520 KB Output is correct
156 Correct 300 ms 460404 KB Output is correct
157 Incorrect 283 ms 462464 KB Output isn't correct
158 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 423304 KB Output is correct
2 Correct 175 ms 423332 KB Output is correct
3 Correct 184 ms 423568 KB Output is correct
4 Correct 172 ms 423672 KB Output is correct
5 Correct 175 ms 423656 KB Output is correct
6 Correct 174 ms 423564 KB Output is correct
7 Correct 176 ms 423664 KB Output is correct
8 Correct 171 ms 423536 KB Output is correct
9 Correct 173 ms 423316 KB Output is correct
10 Correct 175 ms 423260 KB Output is correct
11 Correct 174 ms 423316 KB Output is correct
12 Correct 173 ms 423252 KB Output is correct
13 Correct 172 ms 423392 KB Output is correct
14 Correct 175 ms 423308 KB Output is correct
15 Correct 171 ms 423272 KB Output is correct
16 Correct 172 ms 423656 KB Output is correct
17 Correct 175 ms 423572 KB Output is correct
18 Correct 172 ms 423512 KB Output is correct
19 Correct 207 ms 438904 KB Output is correct
20 Correct 188 ms 434824 KB Output is correct
21 Correct 211 ms 441892 KB Output is correct
22 Correct 210 ms 441488 KB Output is correct
23 Correct 205 ms 438196 KB Output is correct
24 Correct 217 ms 441936 KB Output is correct
25 Correct 193 ms 438220 KB Output is correct
26 Correct 202 ms 441636 KB Output is correct
27 Correct 203 ms 441392 KB Output is correct
28 Correct 198 ms 438356 KB Output is correct
29 Correct 272 ms 462344 KB Output is correct
30 Correct 203 ms 441460 KB Output is correct
31 Correct 239 ms 469976 KB Output is correct
32 Correct 281 ms 468412 KB Output is correct
33 Correct 282 ms 460720 KB Output is correct
34 Correct 247 ms 469724 KB Output is correct
35 Correct 236 ms 460460 KB Output is correct
36 Correct 271 ms 469320 KB Output is correct
37 Correct 267 ms 468512 KB Output is correct
38 Correct 235 ms 460860 KB Output is correct
39 Correct 1365 ms 813788 KB Output is correct
40 Correct 289 ms 475152 KB Output is correct
41 Correct 267 ms 480248 KB Output is correct
42 Correct 336 ms 482908 KB Output is correct
43 Correct 324 ms 492760 KB Output is correct
44 Correct 567 ms 652280 KB Output is correct
45 Correct 587 ms 641556 KB Output is correct
46 Correct 1185 ms 905432 KB Output is correct
47 Correct 1299 ms 875332 KB Output is correct
48 Correct 1280 ms 797304 KB Output is correct
49 Correct 849 ms 887428 KB Output is correct
50 Correct 720 ms 795280 KB Output is correct
51 Correct 1247 ms 882344 KB Output is correct
52 Correct 1186 ms 875588 KB Output is correct
53 Correct 1210 ms 797884 KB Output is correct
54 Correct 190 ms 423272 KB Output is correct
55 Correct 185 ms 423364 KB Output is correct
56 Correct 184 ms 423316 KB Output is correct
57 Correct 193 ms 423240 KB Output is correct
58 Correct 199 ms 423524 KB Output is correct
59 Correct 200 ms 423348 KB Output is correct
60 Correct 183 ms 423368 KB Output is correct
61 Correct 197 ms 423364 KB Output is correct
62 Correct 184 ms 423564 KB Output is correct
63 Correct 190 ms 423664 KB Output is correct
64 Correct 209 ms 423624 KB Output is correct
65 Correct 188 ms 423596 KB Output is correct
66 Correct 209 ms 423500 KB Output is correct
67 Correct 191 ms 423512 KB Output is correct
68 Correct 184 ms 423620 KB Output is correct
69 Correct 185 ms 423600 KB Output is correct
70 Correct 184 ms 423608 KB Output is correct
71 Correct 183 ms 423360 KB Output is correct
72 Correct 193 ms 423516 KB Output is correct
73 Correct 185 ms 423368 KB Output is correct
74 Correct 183 ms 423372 KB Output is correct
75 Correct 186 ms 423520 KB Output is correct
76 Correct 206 ms 423312 KB Output is correct
77 Correct 187 ms 423424 KB Output is correct
78 Correct 184 ms 423356 KB Output is correct
79 Correct 183 ms 423384 KB Output is correct
80 Correct 184 ms 423408 KB Output is correct
81 Correct 202 ms 423496 KB Output is correct
82 Correct 184 ms 423260 KB Output is correct
83 Correct 182 ms 423612 KB Output is correct
84 Correct 182 ms 423608 KB Output is correct
85 Correct 183 ms 423584 KB Output is correct
86 Correct 188 ms 423240 KB Output is correct
87 Correct 188 ms 423340 KB Output is correct
88 Correct 181 ms 423368 KB Output is correct
89 Correct 186 ms 423352 KB Output is correct
90 Correct 183 ms 423368 KB Output is correct
91 Correct 180 ms 423356 KB Output is correct
92 Correct 184 ms 423628 KB Output is correct
93 Correct 183 ms 423656 KB Output is correct
94 Correct 183 ms 423488 KB Output is correct
95 Correct 184 ms 423492 KB Output is correct
96 Correct 192 ms 423452 KB Output is correct
97 Correct 188 ms 423672 KB Output is correct
98 Correct 182 ms 423360 KB Output is correct
99 Correct 184 ms 423456 KB Output is correct
100 Correct 182 ms 423284 KB Output is correct
101 Correct 182 ms 423520 KB Output is correct
102 Correct 182 ms 423420 KB Output is correct
103 Correct 181 ms 423316 KB Output is correct
104 Correct 184 ms 423368 KB Output is correct
105 Correct 183 ms 423324 KB Output is correct
106 Correct 184 ms 423500 KB Output is correct
107 Correct 182 ms 423568 KB Output is correct
108 Correct 195 ms 423604 KB Output is correct
109 Correct 183 ms 423864 KB Output is correct
110 Correct 205 ms 434572 KB Output is correct
111 Correct 222 ms 440504 KB Output is correct
112 Correct 212 ms 441956 KB Output is correct
113 Correct 215 ms 438232 KB Output is correct
114 Correct 216 ms 437840 KB Output is correct
115 Correct 212 ms 436340 KB Output is correct
116 Correct 264 ms 438724 KB Output is correct
117 Correct 215 ms 441788 KB Output is correct
118 Correct 215 ms 441388 KB Output is correct
119 Correct 277 ms 460408 KB Output is correct
120 Correct 297 ms 470168 KB Output is correct
121 Correct 271 ms 460664 KB Output is correct
122 Correct 267 ms 459764 KB Output is correct
123 Correct 257 ms 455928 KB Output is correct
124 Correct 465 ms 558560 KB Output is correct
125 Correct 992 ms 792976 KB Output is correct
126 Correct 1126 ms 905308 KB Output is correct
127 Correct 1085 ms 795852 KB Output is correct
128 Correct 1052 ms 787228 KB Output is correct
129 Correct 932 ms 748196 KB Output is correct
130 Correct 1165 ms 845852 KB Output is correct
131 Correct 1116 ms 845304 KB Output is correct
132 Correct 233 ms 438948 KB Output is correct
133 Correct 188 ms 423920 KB Output is correct
134 Correct 184 ms 424464 KB Output is correct
135 Correct 229 ms 434508 KB Output is correct
136 Correct 206 ms 434980 KB Output is correct
137 Correct 218 ms 440396 KB Output is correct
138 Correct 218 ms 441960 KB Output is correct
139 Correct 230 ms 441440 KB Output is correct
140 Correct 231 ms 438236 KB Output is correct
141 Correct 222 ms 438244 KB Output is correct
142 Correct 218 ms 437836 KB Output is correct
143 Correct 212 ms 436396 KB Output is correct
144 Correct 216 ms 441932 KB Output is correct
145 Correct 207 ms 438300 KB Output is correct
146 Correct 218 ms 438348 KB Output is correct
147 Correct 223 ms 438816 KB Output is correct
148 Correct 218 ms 438840 KB Output is correct
149 Correct 220 ms 438728 KB Output is correct
150 Correct 245 ms 438744 KB Output is correct
151 Correct 214 ms 441792 KB Output is correct
152 Correct 217 ms 441396 KB Output is correct
153 Correct 213 ms 438376 KB Output is correct
154 Correct 281 ms 462504 KB Output is correct
155 Correct 217 ms 441520 KB Output is correct
156 Correct 300 ms 460404 KB Output is correct
157 Incorrect 283 ms 462464 KB Output isn't correct
158 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 423304 KB Output is correct
2 Correct 175 ms 423332 KB Output is correct
3 Correct 184 ms 423568 KB Output is correct
4 Correct 172 ms 423672 KB Output is correct
5 Correct 175 ms 423656 KB Output is correct
6 Correct 174 ms 423564 KB Output is correct
7 Correct 176 ms 423664 KB Output is correct
8 Correct 171 ms 423536 KB Output is correct
9 Correct 173 ms 423316 KB Output is correct
10 Correct 175 ms 423260 KB Output is correct
11 Correct 174 ms 423316 KB Output is correct
12 Correct 173 ms 423252 KB Output is correct
13 Correct 172 ms 423392 KB Output is correct
14 Correct 175 ms 423308 KB Output is correct
15 Correct 171 ms 423272 KB Output is correct
16 Correct 172 ms 423656 KB Output is correct
17 Correct 175 ms 423572 KB Output is correct
18 Correct 172 ms 423512 KB Output is correct
19 Correct 207 ms 438904 KB Output is correct
20 Correct 188 ms 434824 KB Output is correct
21 Correct 211 ms 441892 KB Output is correct
22 Correct 210 ms 441488 KB Output is correct
23 Correct 205 ms 438196 KB Output is correct
24 Correct 217 ms 441936 KB Output is correct
25 Correct 193 ms 438220 KB Output is correct
26 Correct 202 ms 441636 KB Output is correct
27 Correct 203 ms 441392 KB Output is correct
28 Correct 198 ms 438356 KB Output is correct
29 Correct 272 ms 462344 KB Output is correct
30 Correct 203 ms 441460 KB Output is correct
31 Correct 239 ms 469976 KB Output is correct
32 Correct 281 ms 468412 KB Output is correct
33 Correct 282 ms 460720 KB Output is correct
34 Correct 247 ms 469724 KB Output is correct
35 Correct 236 ms 460460 KB Output is correct
36 Correct 271 ms 469320 KB Output is correct
37 Correct 267 ms 468512 KB Output is correct
38 Correct 235 ms 460860 KB Output is correct
39 Correct 1365 ms 813788 KB Output is correct
40 Correct 289 ms 475152 KB Output is correct
41 Correct 267 ms 480248 KB Output is correct
42 Correct 336 ms 482908 KB Output is correct
43 Correct 324 ms 492760 KB Output is correct
44 Correct 567 ms 652280 KB Output is correct
45 Correct 587 ms 641556 KB Output is correct
46 Correct 1185 ms 905432 KB Output is correct
47 Correct 1299 ms 875332 KB Output is correct
48 Correct 1280 ms 797304 KB Output is correct
49 Correct 849 ms 887428 KB Output is correct
50 Correct 720 ms 795280 KB Output is correct
51 Correct 1247 ms 882344 KB Output is correct
52 Correct 1186 ms 875588 KB Output is correct
53 Correct 1210 ms 797884 KB Output is correct
54 Correct 190 ms 423272 KB Output is correct
55 Correct 185 ms 423364 KB Output is correct
56 Correct 184 ms 423316 KB Output is correct
57 Correct 193 ms 423240 KB Output is correct
58 Correct 199 ms 423524 KB Output is correct
59 Correct 200 ms 423348 KB Output is correct
60 Correct 183 ms 423368 KB Output is correct
61 Correct 197 ms 423364 KB Output is correct
62 Correct 184 ms 423564 KB Output is correct
63 Correct 190 ms 423664 KB Output is correct
64 Correct 209 ms 423624 KB Output is correct
65 Correct 188 ms 423596 KB Output is correct
66 Correct 209 ms 423500 KB Output is correct
67 Correct 191 ms 423512 KB Output is correct
68 Correct 184 ms 423620 KB Output is correct
69 Correct 185 ms 423600 KB Output is correct
70 Correct 184 ms 423608 KB Output is correct
71 Correct 183 ms 423360 KB Output is correct
72 Correct 193 ms 423516 KB Output is correct
73 Correct 185 ms 423368 KB Output is correct
74 Correct 183 ms 423372 KB Output is correct
75 Correct 186 ms 423520 KB Output is correct
76 Correct 206 ms 423312 KB Output is correct
77 Correct 187 ms 423424 KB Output is correct
78 Correct 184 ms 423356 KB Output is correct
79 Correct 183 ms 423384 KB Output is correct
80 Correct 184 ms 423408 KB Output is correct
81 Correct 202 ms 423496 KB Output is correct
82 Correct 184 ms 423260 KB Output is correct
83 Correct 182 ms 423612 KB Output is correct
84 Correct 182 ms 423608 KB Output is correct
85 Correct 183 ms 423584 KB Output is correct
86 Correct 188 ms 423240 KB Output is correct
87 Correct 188 ms 423340 KB Output is correct
88 Correct 181 ms 423368 KB Output is correct
89 Correct 186 ms 423352 KB Output is correct
90 Correct 183 ms 423368 KB Output is correct
91 Correct 180 ms 423356 KB Output is correct
92 Correct 184 ms 423628 KB Output is correct
93 Correct 183 ms 423656 KB Output is correct
94 Correct 183 ms 423488 KB Output is correct
95 Correct 184 ms 423492 KB Output is correct
96 Correct 192 ms 423452 KB Output is correct
97 Correct 188 ms 423672 KB Output is correct
98 Correct 182 ms 423360 KB Output is correct
99 Correct 184 ms 423456 KB Output is correct
100 Correct 182 ms 423284 KB Output is correct
101 Correct 182 ms 423520 KB Output is correct
102 Correct 182 ms 423420 KB Output is correct
103 Correct 181 ms 423316 KB Output is correct
104 Correct 184 ms 423368 KB Output is correct
105 Correct 183 ms 423324 KB Output is correct
106 Correct 184 ms 423500 KB Output is correct
107 Correct 182 ms 423568 KB Output is correct
108 Correct 195 ms 423604 KB Output is correct
109 Correct 183 ms 423864 KB Output is correct
110 Correct 205 ms 434572 KB Output is correct
111 Correct 222 ms 440504 KB Output is correct
112 Correct 212 ms 441956 KB Output is correct
113 Correct 215 ms 438232 KB Output is correct
114 Correct 216 ms 437840 KB Output is correct
115 Correct 212 ms 436340 KB Output is correct
116 Correct 264 ms 438724 KB Output is correct
117 Correct 215 ms 441788 KB Output is correct
118 Correct 215 ms 441388 KB Output is correct
119 Correct 277 ms 460408 KB Output is correct
120 Correct 297 ms 470168 KB Output is correct
121 Correct 271 ms 460664 KB Output is correct
122 Correct 267 ms 459764 KB Output is correct
123 Correct 257 ms 455928 KB Output is correct
124 Correct 465 ms 558560 KB Output is correct
125 Correct 992 ms 792976 KB Output is correct
126 Correct 1126 ms 905308 KB Output is correct
127 Correct 1085 ms 795852 KB Output is correct
128 Correct 1052 ms 787228 KB Output is correct
129 Correct 932 ms 748196 KB Output is correct
130 Correct 1165 ms 845852 KB Output is correct
131 Correct 1116 ms 845304 KB Output is correct
132 Correct 233 ms 438948 KB Output is correct
133 Correct 188 ms 423920 KB Output is correct
134 Correct 184 ms 424464 KB Output is correct
135 Correct 229 ms 434508 KB Output is correct
136 Correct 206 ms 434980 KB Output is correct
137 Correct 218 ms 440396 KB Output is correct
138 Correct 218 ms 441960 KB Output is correct
139 Correct 230 ms 441440 KB Output is correct
140 Correct 231 ms 438236 KB Output is correct
141 Correct 222 ms 438244 KB Output is correct
142 Correct 218 ms 437836 KB Output is correct
143 Correct 212 ms 436396 KB Output is correct
144 Correct 216 ms 441932 KB Output is correct
145 Correct 207 ms 438300 KB Output is correct
146 Correct 218 ms 438348 KB Output is correct
147 Correct 223 ms 438816 KB Output is correct
148 Correct 218 ms 438840 KB Output is correct
149 Correct 220 ms 438728 KB Output is correct
150 Correct 245 ms 438744 KB Output is correct
151 Correct 214 ms 441792 KB Output is correct
152 Correct 217 ms 441396 KB Output is correct
153 Correct 213 ms 438376 KB Output is correct
154 Correct 281 ms 462504 KB Output is correct
155 Correct 217 ms 441520 KB Output is correct
156 Correct 300 ms 460404 KB Output is correct
157 Incorrect 283 ms 462464 KB Output isn't correct
158 Halted 0 ms 0 KB -