oj.uz

Submission #780279

# Submission time Handle Problem Language Result Execution time Memory
780279 2023-07-12T07:53:00 Z boris_mihov Maze (JOI23_ho_t3) C++17
51 / 100
 2000 ms 671112 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>

typedef long long llong;
const int MAXLOG = 23;
const int MAXN = 6000000 + 10;
const int INF  = 1e9;

struct BIT
{
    std::vector <int> tree;
    void build(int sz)
    {
        tree.resize(sz + 1, 0);
    }

    void update(int pos, int value)
    {
        for (int idx = pos ; idx < tree.size() ; idx += idx & (-idx))
        {
            tree[idx] += value;
        }
    }

    int query(int pos)
    {
        int res = 0;
        for (int idx = pos ; idx > 0 ; idx -= idx & (-idx))
        {
            res += tree[idx];
        }

        return pos - res;
    }

    int findKth(int k)
    {
        int idx = 0;
        for (int log = MAXLOG - 1 ; log >= 0 ; --log)
        {
            if (idx + (1 << log) < tree.size() && (1 << log) - tree[idx + (1 << log)] < k)
            {
                idx += (1 << log);
                k -= (1 << log) - tree[idx];
            }
        }

        return idx + 1;
    }
};

int r, c, n;
int sRow, sCol;
int eRow, eCol;
BIT byROW[MAXN];
BIT byCOL[MAXN];
std::pair <int,int> delta[] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
std::deque <std::pair <int,int>> dq;
std::vector <int> dist[MAXN];
std::string t[MAXN];

bool isOutside(int row, int col)
{
    return row == 0 || row == r + 1 || col == 0 || col == c + 1;
}

void setCELL(int row, int col)
{
    byROW[row].update(col, 1); 
    byCOL[col].update(row, 1); 
}

void addROW(int row, int colL, int colR, int currDist)
{
    int curr = byROW[row].query(colL - 1);
    // while (true)
    // {
    //     int search = byROW[row].findKth(curr + 1);
    //     if (search > colR)
    //     {
    //         break;
    //     }

    //     if (dist[row][search] > currDist + 1) dist[row][search] = currDist + 1;
    //     dq.push_back({row, search});
    //     setCELL(row, search);
    // }

    for (int i = colL ; i <= colR ; ++i)
    {
        if (dist[row][i] == INF)
        {
            if (byROW[row].findKth(curr + 1) != i)
            {
                int res = byROW[row].findKth(curr + 1); assert(res != i);
                // assert(byROW[row].query(res) - byROW[row].query(res - 1) == 1);
                bool was = (res > i);
                while (res < i){}
                while (res > i){}
                assert(res != i && (res > i) == was);
                // while (true) assert((res > i) == was);
            }

            setCELL(row, i);
            dist[row][i] = currDist + 1;
            dq.push_back({row, i});
        }
    }
}

void addCOL(int col, int rowL, int rowR, int currDist)
{
    int curr = byCOL[col].query(rowL - 1);
    // while (true)
    // {
    //     int search = byCOL[col].findKth(curr + 1);
    //     if (search > rowR)
    //     {
    //         break;
    //     }

    //     if (dist[search][col] > currDist + 1) dist[search][col] = currDist + 1;
    //     dq.push_back({search, col});
    //     setCELL(search, col);
    // }

    for (int i = rowL ; i <= rowR ; ++i)
    {
        if (dist[i][col] == INF)
        {
            if (byCOL[col].findKth(curr + 1) != i)
            {
                int res = byCOL[col].findKth(curr + 1); assert(res != i);
                // assert(byCOL[col].query(res) - byCOL[col].query(res - 1) == 1);
                bool was = (res > i);
                while (res < i){}
                while (res > i){}
                assert(res != i && (res > i) == was);
                // while (true) assert((res > i) == was);
            }

            setCELL(i, col);
            dist[i][col] = currDist + 1;
            dq.push_back({i, col});
        }
    }
}

void solve()
{
    for (int i = 1 ; i <= r ; ++i)
    {
        std::fill(dist[i].begin(), dist[i].end(), INF);
    }

    for (int i = 1 ; i <= r ; ++i)
    {
        byROW[i].build(c);
    }
    
    for (int i = 1 ; i <= c ; ++i)
    {
        byCOL[i].build(r);
    }
    
    dq.push_back({sRow, sCol});
    dist[sRow][sCol] = 0;
    setCELL(sRow, sCol);

    while (!dq.empty())
    {
        auto [row, col] = dq.front();
        dq.pop_front();    

        if (row == eRow && col == eCol)
        {
            std::cout << dist[row][col] << '\n';
            break;
        }

        for (const auto &[dx, dy] : delta)
        {
            if (isOutside(row + dx, col + dy) || dist[row + dx][col + dy] <= dist[row][col])
            {
                continue;
            }

            if (t[row + dx][col + dy] == '.')
            {
                setCELL(row + dx, col + dy);
                dist[row + dx][col + dy] = dist[row][col]; 
                dq.push_front({row + dx, col + dy});
            }
        }

        if (abs(row - eRow) <= n && abs(col - eCol) <= n && dist[eRow][eCol] > dist[row][col])
        {
            setCELL(eRow, eCol);
            dist[eRow][eCol] = dist[row][col] + 1;
            dq.push_back({eRow, eCol});
        }

        addROW(std::max(1, row - n), std::max(1, col - n + 1), std::min(c, col + n - 1), dist[row][col]);
        addROW(std::min(r, row + n), std::max(1, col - n + 1), std::min(c, col + n - 1), dist[row][col]);
        addCOL(std::max(1, col - n), std::max(1, row - n + 1), std::min(r, row + n - 1), dist[row][col]);
        addCOL(std::min(c, col + n), std::max(1, row - n + 1), std::min(r, row + n - 1), dist[row][col]);
    }
}

void input()
{
    std::cin >> r >> c >> n;
    std::cin >> sRow >> sCol;
    std::cin >> eRow >> eCol;
    for (int i = 1 ; i <= r ; ++i)
    {
        std::cin >> t[i];
        t[i] = ' ' + t[i];
        dist[i].resize(c + 1, INF);
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Compilation message

Main.cpp: In member function 'void BIT::update(int, int)':
Main.cpp:23:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for (int idx = pos ; idx < tree.size() ; idx += idx & (-idx))
      |                              ~~~~^~~~~~~~~~~~~
Main.cpp: In member function 'int BIT::findKth(int)':
Main.cpp:45:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             if (idx + (1 << log) < tree.size() && (1 << log) - tree[idx + (1 << log)] < k)
      |                 ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 610768 KB Output is correct
2 Correct 280 ms 610804 KB Output is correct
3 Correct 271 ms 610880 KB Output is correct
4 Correct 248 ms 610840 KB Output is correct
5 Correct 258 ms 610788 KB Output is correct
6 Correct 262 ms 610812 KB Output is correct
7 Correct 250 ms 610824 KB Output is correct
8 Correct 250 ms 610868 KB Output is correct
9 Correct 251 ms 610776 KB Output is correct
10 Correct 262 ms 610864 KB Output is correct
11 Correct 282 ms 610780 KB Output is correct
12 Correct 275 ms 610748 KB Output is correct
13 Correct 279 ms 610868 KB Output is correct
14 Correct 282 ms 610872 KB Output is correct
15 Correct 269 ms 610864 KB Output is correct
16 Correct 271 ms 610792 KB Output is correct
17 Correct 254 ms 610816 KB Output is correct
18 Correct 274 ms 610792 KB Output is correct
19 Correct 266 ms 611648 KB Output is correct
20 Correct 264 ms 612732 KB Output is correct
21 Correct 264 ms 611892 KB Output is correct
22 Correct 261 ms 611656 KB Output is correct
23 Correct 277 ms 611644 KB Output is correct
24 Correct 266 ms 613288 KB Output is correct
25 Correct 265 ms 613280 KB Output is correct
26 Correct 258 ms 611672 KB Output is correct
27 Correct 250 ms 611568 KB Output is correct
28 Correct 255 ms 611528 KB Output is correct
29 Correct 271 ms 612812 KB Output is correct
30 Correct 263 ms 612308 KB Output is correct
31 Correct 257 ms 612988 KB Output is correct
32 Correct 276 ms 612808 KB Output is correct
33 Correct 257 ms 612816 KB Output is correct
34 Correct 274 ms 616784 KB Output is correct
35 Correct 275 ms 616892 KB Output is correct
36 Correct 271 ms 612868 KB Output is correct
37 Correct 265 ms 612844 KB Output is correct
38 Correct 259 ms 612784 KB Output is correct
39 Correct 398 ms 630068 KB Output is correct
40 Correct 247 ms 613108 KB Output is correct
41 Correct 273 ms 618292 KB Output is correct
42 Correct 284 ms 613724 KB Output is correct
43 Correct 276 ms 616780 KB Output is correct
44 Correct 278 ms 623152 KB Output is correct
45 Correct 295 ms 622980 KB Output is correct
46 Correct 338 ms 636324 KB Output is correct
47 Correct 375 ms 630100 KB Output is correct
48 Correct 371 ms 630072 KB Output is correct
49 Correct 383 ms 671112 KB Output is correct
50 Correct 361 ms 671052 KB Output is correct
51 Correct 348 ms 630312 KB Output is correct
52 Correct 332 ms 630160 KB Output is correct
53 Correct 366 ms 629992 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 610768 KB Output is correct
2 Correct 258 ms 610868 KB Output is correct
3 Correct 254 ms 610764 KB Output is correct
4 Correct 253 ms 610868 KB Output is correct
5 Correct 254 ms 610880 KB Output is correct
6 Correct 260 ms 610860 KB Output is correct
7 Correct 252 ms 610872 KB Output is correct
8 Correct 254 ms 610868 KB Output is correct
9 Correct 257 ms 610880 KB Output is correct
10 Correct 268 ms 610776 KB Output is correct
11 Correct 259 ms 610880 KB Output is correct
12 Correct 255 ms 610796 KB Output is correct
13 Correct 264 ms 610880 KB Output is correct
14 Correct 264 ms 610876 KB Output is correct
15 Correct 269 ms 610904 KB Output is correct
16 Correct 267 ms 610892 KB Output is correct
17 Correct 267 ms 610892 KB Output is correct
18 Correct 261 ms 610748 KB Output is correct
19 Correct 254 ms 610876 KB Output is correct
20 Correct 256 ms 610820 KB Output is correct
21 Correct 255 ms 610760 KB Output is correct
22 Correct 259 ms 610836 KB Output is correct
23 Correct 261 ms 610824 KB Output is correct
24 Correct 273 ms 610816 KB Output is correct
25 Correct 253 ms 610740 KB Output is correct
26 Correct 255 ms 610868 KB Output is correct
27 Correct 258 ms 610912 KB Output is correct
28 Correct 255 ms 610828 KB Output is correct
29 Correct 264 ms 610788 KB Output is correct
30 Correct 259 ms 610780 KB Output is correct
31 Correct 249 ms 610876 KB Output is correct
32 Correct 250 ms 610768 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 610880 KB Output is correct
2 Correct 262 ms 610868 KB Output is correct
3 Correct 258 ms 610860 KB Output is correct
4 Correct 253 ms 611036 KB Output is correct
5 Correct 250 ms 610864 KB Output is correct
6 Correct 250 ms 610792 KB Output is correct
7 Correct 255 ms 610828 KB Output is correct
8 Correct 251 ms 610880 KB Output is correct
9 Correct 248 ms 610776 KB Output is correct
10 Correct 261 ms 610864 KB Output is correct
11 Correct 250 ms 610876 KB Output is correct
12 Correct 251 ms 610792 KB Output is correct
13 Correct 250 ms 610736 KB Output is correct
14 Correct 251 ms 610768 KB Output is correct
15 Correct 268 ms 610824 KB Output is correct
16 Correct 263 ms 610764 KB Output is correct
17 Correct 252 ms 610828 KB Output is correct
18 Correct 252 ms 610800 KB Output is correct
19 Correct 255 ms 610796 KB Output is correct
20 Correct 249 ms 610876 KB Output is correct
21 Correct 248 ms 610788 KB Output is correct
22 Correct 257 ms 610880 KB Output is correct
23 Correct 265 ms 610780 KB Output is correct
24 Correct 353 ms 610836 KB Output is correct
25 Correct 271 ms 611380 KB Output is correct
26 Correct 260 ms 611920 KB Output is correct
27 Correct 256 ms 611788 KB Output is correct
28 Correct 271 ms 611716 KB Output is correct
29 Correct 256 ms 611656 KB Output is correct
30 Correct 258 ms 611576 KB Output is correct
31 Correct 265 ms 611728 KB Output is correct
32 Correct 263 ms 611652 KB Output is correct
33 Correct 256 ms 611540 KB Output is correct
34 Correct 289 ms 613580 KB Output is correct
35 Correct 268 ms 613020 KB Output is correct
36 Correct 429 ms 613472 KB Output is correct
37 Correct 261 ms 612812 KB Output is correct
38 Correct 252 ms 612796 KB Output is correct
39 Correct 334 ms 620452 KB Output is correct
40 Correct 480 ms 638268 KB Output is correct
41 Correct 347 ms 636236 KB Output is correct
42 Execution timed out 2094 ms 637388 KB Time limit exceeded
43 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 610768 KB Output is correct
2 Correct 258 ms 610868 KB Output is correct
3 Correct 254 ms 610764 KB Output is correct
4 Correct 253 ms 610868 KB Output is correct
5 Correct 254 ms 610880 KB Output is correct
6 Correct 260 ms 610860 KB Output is correct
7 Correct 252 ms 610872 KB Output is correct
8 Correct 254 ms 610868 KB Output is correct
9 Correct 257 ms 610880 KB Output is correct
10 Correct 268 ms 610776 KB Output is correct
11 Correct 259 ms 610880 KB Output is correct
12 Correct 255 ms 610796 KB Output is correct
13 Correct 264 ms 610880 KB Output is correct
14 Correct 264 ms 610876 KB Output is correct
15 Correct 269 ms 610904 KB Output is correct
16 Correct 267 ms 610892 KB Output is correct
17 Correct 267 ms 610892 KB Output is correct
18 Correct 261 ms 610748 KB Output is correct
19 Correct 254 ms 610876 KB Output is correct
20 Correct 256 ms 610820 KB Output is correct
21 Correct 255 ms 610760 KB Output is correct
22 Correct 259 ms 610836 KB Output is correct
23 Correct 261 ms 610824 KB Output is correct
24 Correct 273 ms 610816 KB Output is correct
25 Correct 253 ms 610740 KB Output is correct
26 Correct 255 ms 610868 KB Output is correct
27 Correct 258 ms 610912 KB Output is correct
28 Correct 255 ms 610828 KB Output is correct
29 Correct 264 ms 610788 KB Output is correct
30 Correct 259 ms 610780 KB Output is correct
31 Correct 249 ms 610876 KB Output is correct
32 Correct 250 ms 610768 KB Output is correct
33 Correct 255 ms 611612 KB Output is correct
34 Correct 259 ms 610832 KB Output is correct
35 Correct 248 ms 610892 KB Output is correct
36 Correct 254 ms 611300 KB Output is correct
37 Correct 266 ms 612728 KB Output is correct
38 Correct 256 ms 611924 KB Output is correct
39 Correct 253 ms 611788 KB Output is correct
40 Correct 259 ms 611776 KB Output is correct
41 Correct 259 ms 611612 KB Output is correct
42 Correct 254 ms 611652 KB Output is correct
43 Correct 253 ms 611788 KB Output is correct
44 Correct 252 ms 611532 KB Output is correct
45 Correct 253 ms 613236 KB Output is correct
46 Correct 266 ms 613324 KB Output is correct
47 Correct 259 ms 612268 KB Output is correct
48 Correct 254 ms 611660 KB Output is correct
49 Correct 260 ms 611724 KB Output is correct
50 Correct 260 ms 611632 KB Output is correct
51 Correct 258 ms 611716 KB Output is correct
52 Correct 255 ms 611656 KB Output is correct
53 Correct 249 ms 611636 KB Output is correct
54 Correct 257 ms 611656 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 610768 KB Output is correct
2 Correct 258 ms 610868 KB Output is correct
3 Correct 254 ms 610764 KB Output is correct
4 Correct 253 ms 610868 KB Output is correct
5 Correct 254 ms 610880 KB Output is correct
6 Correct 260 ms 610860 KB Output is correct
7 Correct 252 ms 610872 KB Output is correct
8 Correct 254 ms 610868 KB Output is correct
9 Correct 257 ms 610880 KB Output is correct
10 Correct 268 ms 610776 KB Output is correct
11 Correct 259 ms 610880 KB Output is correct
12 Correct 255 ms 610796 KB Output is correct
13 Correct 264 ms 610880 KB Output is correct
14 Correct 264 ms 610876 KB Output is correct
15 Correct 269 ms 610904 KB Output is correct
16 Correct 267 ms 610892 KB Output is correct
17 Correct 267 ms 610892 KB Output is correct
18 Correct 261 ms 610748 KB Output is correct
19 Correct 254 ms 610876 KB Output is correct
20 Correct 256 ms 610820 KB Output is correct
21 Correct 255 ms 610760 KB Output is correct
22 Correct 259 ms 610836 KB Output is correct
23 Correct 261 ms 610824 KB Output is correct
24 Correct 273 ms 610816 KB Output is correct
25 Correct 253 ms 610740 KB Output is correct
26 Correct 255 ms 610868 KB Output is correct
27 Correct 258 ms 610912 KB Output is correct
28 Correct 255 ms 610828 KB Output is correct
29 Correct 264 ms 610788 KB Output is correct
30 Correct 259 ms 610780 KB Output is correct
31 Correct 249 ms 610876 KB Output is correct
32 Correct 250 ms 610768 KB Output is correct
33 Correct 255 ms 611612 KB Output is correct
34 Correct 259 ms 610832 KB Output is correct
35 Correct 248 ms 610892 KB Output is correct
36 Correct 254 ms 611300 KB Output is correct
37 Correct 266 ms 612728 KB Output is correct
38 Correct 256 ms 611924 KB Output is correct
39 Correct 253 ms 611788 KB Output is correct
40 Correct 259 ms 611776 KB Output is correct
41 Correct 259 ms 611612 KB Output is correct
42 Correct 254 ms 611652 KB Output is correct
43 Correct 253 ms 611788 KB Output is correct
44 Correct 252 ms 611532 KB Output is correct
45 Correct 253 ms 613236 KB Output is correct
46 Correct 266 ms 613324 KB Output is correct
47 Correct 259 ms 612268 KB Output is correct
48 Correct 254 ms 611660 KB Output is correct
49 Correct 260 ms 611724 KB Output is correct
50 Correct 260 ms 611632 KB Output is correct
51 Correct 258 ms 611716 KB Output is correct
52 Correct 255 ms 611656 KB Output is correct
53 Correct 249 ms 611636 KB Output is correct
54 Correct 257 ms 611656 KB Output is correct
55 Correct 262 ms 612768 KB Output is correct
56 Correct 259 ms 612372 KB Output is correct
57 Correct 285 ms 613584 KB Output is correct
58 Correct 261 ms 612720 KB Output is correct
59 Correct 251 ms 612940 KB Output is correct
60 Correct 278 ms 612824 KB Output is correct
61 Correct 265 ms 612776 KB Output is correct
62 Correct 418 ms 613452 KB Output is correct
63 Correct 253 ms 612768 KB Output is correct
64 Correct 250 ms 612824 KB Output is correct
65 Correct 263 ms 616824 KB Output is correct
66 Correct 269 ms 616784 KB Output is correct
67 Correct 271 ms 614460 KB Output is correct
68 Correct 269 ms 612820 KB Output is correct
69 Correct 274 ms 612812 KB Output is correct
70 Correct 288 ms 613008 KB Output is correct
71 Correct 296 ms 613016 KB Output is correct
72 Correct 254 ms 612824 KB Output is correct
73 Correct 271 ms 612820 KB Output is correct
74 Correct 255 ms 612808 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 610768 KB Output is correct
2 Correct 280 ms 610804 KB Output is correct
3 Correct 271 ms 610880 KB Output is correct
4 Correct 248 ms 610840 KB Output is correct
5 Correct 258 ms 610788 KB Output is correct
6 Correct 262 ms 610812 KB Output is correct
7 Correct 250 ms 610824 KB Output is correct
8 Correct 250 ms 610868 KB Output is correct
9 Correct 251 ms 610776 KB Output is correct
10 Correct 262 ms 610864 KB Output is correct
11 Correct 282 ms 610780 KB Output is correct
12 Correct 275 ms 610748 KB Output is correct
13 Correct 279 ms 610868 KB Output is correct
14 Correct 282 ms 610872 KB Output is correct
15 Correct 269 ms 610864 KB Output is correct
16 Correct 271 ms 610792 KB Output is correct
17 Correct 254 ms 610816 KB Output is correct
18 Correct 274 ms 610792 KB Output is correct
19 Correct 266 ms 611648 KB Output is correct
20 Correct 264 ms 612732 KB Output is correct
21 Correct 264 ms 611892 KB Output is correct
22 Correct 261 ms 611656 KB Output is correct
23 Correct 277 ms 611644 KB Output is correct
24 Correct 266 ms 613288 KB Output is correct
25 Correct 265 ms 613280 KB Output is correct
26 Correct 258 ms 611672 KB Output is correct
27 Correct 250 ms 611568 KB Output is correct
28 Correct 255 ms 611528 KB Output is correct
29 Correct 271 ms 612812 KB Output is correct
30 Correct 263 ms 612308 KB Output is correct
31 Correct 257 ms 612988 KB Output is correct
32 Correct 276 ms 612808 KB Output is correct
33 Correct 257 ms 612816 KB Output is correct
34 Correct 274 ms 616784 KB Output is correct
35 Correct 275 ms 616892 KB Output is correct
36 Correct 271 ms 612868 KB Output is correct
37 Correct 265 ms 612844 KB Output is correct
38 Correct 259 ms 612784 KB Output is correct
39 Correct 398 ms 630068 KB Output is correct
40 Correct 247 ms 613108 KB Output is correct
41 Correct 273 ms 618292 KB Output is correct
42 Correct 284 ms 613724 KB Output is correct
43 Correct 276 ms 616780 KB Output is correct
44 Correct 278 ms 623152 KB Output is correct
45 Correct 295 ms 622980 KB Output is correct
46 Correct 338 ms 636324 KB Output is correct
47 Correct 375 ms 630100 KB Output is correct
48 Correct 371 ms 630072 KB Output is correct
49 Correct 383 ms 671112 KB Output is correct
50 Correct 361 ms 671052 KB Output is correct
51 Correct 348 ms 630312 KB Output is correct
52 Correct 332 ms 630160 KB Output is correct
53 Correct 366 ms 629992 KB Output is correct
54 Correct 263 ms 610768 KB Output is correct
55 Correct 258 ms 610868 KB Output is correct
56 Correct 254 ms 610764 KB Output is correct
57 Correct 253 ms 610868 KB Output is correct
58 Correct 254 ms 610880 KB Output is correct
59 Correct 260 ms 610860 KB Output is correct
60 Correct 252 ms 610872 KB Output is correct
61 Correct 254 ms 610868 KB Output is correct
62 Correct 257 ms 610880 KB Output is correct
63 Correct 268 ms 610776 KB Output is correct
64 Correct 259 ms 610880 KB Output is correct
65 Correct 255 ms 610796 KB Output is correct
66 Correct 264 ms 610880 KB Output is correct
67 Correct 264 ms 610876 KB Output is correct
68 Correct 269 ms 610904 KB Output is correct
69 Correct 267 ms 610892 KB Output is correct
70 Correct 267 ms 610892 KB Output is correct
71 Correct 261 ms 610748 KB Output is correct
72 Correct 254 ms 610876 KB Output is correct
73 Correct 256 ms 610820 KB Output is correct
74 Correct 255 ms 610760 KB Output is correct
75 Correct 259 ms 610836 KB Output is correct
76 Correct 261 ms 610824 KB Output is correct
77 Correct 273 ms 610816 KB Output is correct
78 Correct 253 ms 610740 KB Output is correct
79 Correct 255 ms 610868 KB Output is correct
80 Correct 258 ms 610912 KB Output is correct
81 Correct 255 ms 610828 KB Output is correct
82 Correct 264 ms 610788 KB Output is correct
83 Correct 259 ms 610780 KB Output is correct
84 Correct 249 ms 610876 KB Output is correct
85 Correct 250 ms 610768 KB Output is correct
86 Correct 253 ms 610880 KB Output is correct
87 Correct 262 ms 610868 KB Output is correct
88 Correct 258 ms 610860 KB Output is correct
89 Correct 253 ms 611036 KB Output is correct
90 Correct 250 ms 610864 KB Output is correct
91 Correct 250 ms 610792 KB Output is correct
92 Correct 255 ms 610828 KB Output is correct
93 Correct 251 ms 610880 KB Output is correct
94 Correct 248 ms 610776 KB Output is correct
95 Correct 261 ms 610864 KB Output is correct
96 Correct 250 ms 610876 KB Output is correct
97 Correct 251 ms 610792 KB Output is correct
98 Correct 250 ms 610736 KB Output is correct
99 Correct 251 ms 610768 KB Output is correct
100 Correct 268 ms 610824 KB Output is correct
101 Correct 263 ms 610764 KB Output is correct
102 Correct 252 ms 610828 KB Output is correct
103 Correct 252 ms 610800 KB Output is correct
104 Correct 255 ms 610796 KB Output is correct
105 Correct 249 ms 610876 KB Output is correct
106 Correct 248 ms 610788 KB Output is correct
107 Correct 257 ms 610880 KB Output is correct
108 Correct 265 ms 610780 KB Output is correct
109 Correct 353 ms 610836 KB Output is correct
110 Correct 271 ms 611380 KB Output is correct
111 Correct 260 ms 611920 KB Output is correct
112 Correct 256 ms 611788 KB Output is correct
113 Correct 271 ms 611716 KB Output is correct
114 Correct 256 ms 611656 KB Output is correct
115 Correct 258 ms 611576 KB Output is correct
116 Correct 265 ms 611728 KB Output is correct
117 Correct 263 ms 611652 KB Output is correct
118 Correct 256 ms 611540 KB Output is correct
119 Correct 289 ms 613580 KB Output is correct
120 Correct 268 ms 613020 KB Output is correct
121 Correct 429 ms 613472 KB Output is correct
122 Correct 261 ms 612812 KB Output is correct
123 Correct 252 ms 612796 KB Output is correct
124 Correct 334 ms 620452 KB Output is correct
125 Correct 480 ms 638268 KB Output is correct
126 Correct 347 ms 636236 KB Output is correct
127 Execution timed out 2094 ms 637388 KB Time limit exceeded
128 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 610768 KB Output is correct
2 Correct 280 ms 610804 KB Output is correct
3 Correct 271 ms 610880 KB Output is correct
4 Correct 248 ms 610840 KB Output is correct
5 Correct 258 ms 610788 KB Output is correct
6 Correct 262 ms 610812 KB Output is correct
7 Correct 250 ms 610824 KB Output is correct
8 Correct 250 ms 610868 KB Output is correct
9 Correct 251 ms 610776 KB Output is correct
10 Correct 262 ms 610864 KB Output is correct
11 Correct 282 ms 610780 KB Output is correct
12 Correct 275 ms 610748 KB Output is correct
13 Correct 279 ms 610868 KB Output is correct
14 Correct 282 ms 610872 KB Output is correct
15 Correct 269 ms 610864 KB Output is correct
16 Correct 271 ms 610792 KB Output is correct
17 Correct 254 ms 610816 KB Output is correct
18 Correct 274 ms 610792 KB Output is correct
19 Correct 266 ms 611648 KB Output is correct
20 Correct 264 ms 612732 KB Output is correct
21 Correct 264 ms 611892 KB Output is correct
22 Correct 261 ms 611656 KB Output is correct
23 Correct 277 ms 611644 KB Output is correct
24 Correct 266 ms 613288 KB Output is correct
25 Correct 265 ms 613280 KB Output is correct
26 Correct 258 ms 611672 KB Output is correct
27 Correct 250 ms 611568 KB Output is correct
28 Correct 255 ms 611528 KB Output is correct
29 Correct 271 ms 612812 KB Output is correct
30 Correct 263 ms 612308 KB Output is correct
31 Correct 257 ms 612988 KB Output is correct
32 Correct 276 ms 612808 KB Output is correct
33 Correct 257 ms 612816 KB Output is correct
34 Correct 274 ms 616784 KB Output is correct
35 Correct 275 ms 616892 KB Output is correct
36 Correct 271 ms 612868 KB Output is correct
37 Correct 265 ms 612844 KB Output is correct
38 Correct 259 ms 612784 KB Output is correct
39 Correct 398 ms 630068 KB Output is correct
40 Correct 247 ms 613108 KB Output is correct
41 Correct 273 ms 618292 KB Output is correct
42 Correct 284 ms 613724 KB Output is correct
43 Correct 276 ms 616780 KB Output is correct
44 Correct 278 ms 623152 KB Output is correct
45 Correct 295 ms 622980 KB Output is correct
46 Correct 338 ms 636324 KB Output is correct
47 Correct 375 ms 630100 KB Output is correct
48 Correct 371 ms 630072 KB Output is correct
49 Correct 383 ms 671112 KB Output is correct
50 Correct 361 ms 671052 KB Output is correct
51 Correct 348 ms 630312 KB Output is correct
52 Correct 332 ms 630160 KB Output is correct
53 Correct 366 ms 629992 KB Output is correct
54 Correct 263 ms 610768 KB Output is correct
55 Correct 258 ms 610868 KB Output is correct
56 Correct 254 ms 610764 KB Output is correct
57 Correct 253 ms 610868 KB Output is correct
58 Correct 254 ms 610880 KB Output is correct
59 Correct 260 ms 610860 KB Output is correct
60 Correct 252 ms 610872 KB Output is correct
61 Correct 254 ms 610868 KB Output is correct
62 Correct 257 ms 610880 KB Output is correct
63 Correct 268 ms 610776 KB Output is correct
64 Correct 259 ms 610880 KB Output is correct
65 Correct 255 ms 610796 KB Output is correct
66 Correct 264 ms 610880 KB Output is correct
67 Correct 264 ms 610876 KB Output is correct
68 Correct 269 ms 610904 KB Output is correct
69 Correct 267 ms 610892 KB Output is correct
70 Correct 267 ms 610892 KB Output is correct
71 Correct 261 ms 610748 KB Output is correct
72 Correct 254 ms 610876 KB Output is correct
73 Correct 256 ms 610820 KB Output is correct
74 Correct 255 ms 610760 KB Output is correct
75 Correct 259 ms 610836 KB Output is correct
76 Correct 261 ms 610824 KB Output is correct
77 Correct 273 ms 610816 KB Output is correct
78 Correct 253 ms 610740 KB Output is correct
79 Correct 255 ms 610868 KB Output is correct
80 Correct 258 ms 610912 KB Output is correct
81 Correct 255 ms 610828 KB Output is correct
82 Correct 264 ms 610788 KB Output is correct
83 Correct 259 ms 610780 KB Output is correct
84 Correct 249 ms 610876 KB Output is correct
85 Correct 250 ms 610768 KB Output is correct
86 Correct 253 ms 610880 KB Output is correct
87 Correct 262 ms 610868 KB Output is correct
88 Correct 258 ms 610860 KB Output is correct
89 Correct 253 ms 611036 KB Output is correct
90 Correct 250 ms 610864 KB Output is correct
91 Correct 250 ms 610792 KB Output is correct
92 Correct 255 ms 610828 KB Output is correct
93 Correct 251 ms 610880 KB Output is correct
94 Correct 248 ms 610776 KB Output is correct
95 Correct 261 ms 610864 KB Output is correct
96 Correct 250 ms 610876 KB Output is correct
97 Correct 251 ms 610792 KB Output is correct
98 Correct 250 ms 610736 KB Output is correct
99 Correct 251 ms 610768 KB Output is correct
100 Correct 268 ms 610824 KB Output is correct
101 Correct 263 ms 610764 KB Output is correct
102 Correct 252 ms 610828 KB Output is correct
103 Correct 252 ms 610800 KB Output is correct
104 Correct 255 ms 610796 KB Output is correct
105 Correct 249 ms 610876 KB Output is correct
106 Correct 248 ms 610788 KB Output is correct
107 Correct 257 ms 610880 KB Output is correct
108 Correct 265 ms 610780 KB Output is correct
109 Correct 353 ms 610836 KB Output is correct
110 Correct 271 ms 611380 KB Output is correct
111 Correct 260 ms 611920 KB Output is correct
112 Correct 256 ms 611788 KB Output is correct
113 Correct 271 ms 611716 KB Output is correct
114 Correct 256 ms 611656 KB Output is correct
115 Correct 258 ms 611576 KB Output is correct
116 Correct 265 ms 611728 KB Output is correct
117 Correct 263 ms 611652 KB Output is correct
118 Correct 256 ms 611540 KB Output is correct
119 Correct 289 ms 613580 KB Output is correct
120 Correct 268 ms 613020 KB Output is correct
121 Correct 429 ms 613472 KB Output is correct
122 Correct 261 ms 612812 KB Output is correct
123 Correct 252 ms 612796 KB Output is correct
124 Correct 334 ms 620452 KB Output is correct
125 Correct 480 ms 638268 KB Output is correct
126 Correct 347 ms 636236 KB Output is correct
127 Execution timed out 2094 ms 637388 KB Time limit exceeded
128 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 610768 KB Output is correct
2 Correct 280 ms 610804 KB Output is correct
3 Correct 271 ms 610880 KB Output is correct
4 Correct 248 ms 610840 KB Output is correct
5 Correct 258 ms 610788 KB Output is correct
6 Correct 262 ms 610812 KB Output is correct
7 Correct 250 ms 610824 KB Output is correct
8 Correct 250 ms 610868 KB Output is correct
9 Correct 251 ms 610776 KB Output is correct
10 Correct 262 ms 610864 KB Output is correct
11 Correct 282 ms 610780 KB Output is correct
12 Correct 275 ms 610748 KB Output is correct
13 Correct 279 ms 610868 KB Output is correct
14 Correct 282 ms 610872 KB Output is correct
15 Correct 269 ms 610864 KB Output is correct
16 Correct 271 ms 610792 KB Output is correct
17 Correct 254 ms 610816 KB Output is correct
18 Correct 274 ms 610792 KB Output is correct
19 Correct 266 ms 611648 KB Output is correct
20 Correct 264 ms 612732 KB Output is correct
21 Correct 264 ms 611892 KB Output is correct
22 Correct 261 ms 611656 KB Output is correct
23 Correct 277 ms 611644 KB Output is correct
24 Correct 266 ms 613288 KB Output is correct
25 Correct 265 ms 613280 KB Output is correct
26 Correct 258 ms 611672 KB Output is correct
27 Correct 250 ms 611568 KB Output is correct
28 Correct 255 ms 611528 KB Output is correct
29 Correct 271 ms 612812 KB Output is correct
30 Correct 263 ms 612308 KB Output is correct
31 Correct 257 ms 612988 KB Output is correct
32 Correct 276 ms 612808 KB Output is correct
33 Correct 257 ms 612816 KB Output is correct
34 Correct 274 ms 616784 KB Output is correct
35 Correct 275 ms 616892 KB Output is correct
36 Correct 271 ms 612868 KB Output is correct
37 Correct 265 ms 612844 KB Output is correct
38 Correct 259 ms 612784 KB Output is correct
39 Correct 398 ms 630068 KB Output is correct
40 Correct 247 ms 613108 KB Output is correct
41 Correct 273 ms 618292 KB Output is correct
42 Correct 284 ms 613724 KB Output is correct
43 Correct 276 ms 616780 KB Output is correct
44 Correct 278 ms 623152 KB Output is correct
45 Correct 295 ms 622980 KB Output is correct
46 Correct 338 ms 636324 KB Output is correct
47 Correct 375 ms 630100 KB Output is correct
48 Correct 371 ms 630072 KB Output is correct
49 Correct 383 ms 671112 KB Output is correct
50 Correct 361 ms 671052 KB Output is correct
51 Correct 348 ms 630312 KB Output is correct
52 Correct 332 ms 630160 KB Output is correct
53 Correct 366 ms 629992 KB Output is correct
54 Correct 263 ms 610768 KB Output is correct
55 Correct 258 ms 610868 KB Output is correct
56 Correct 254 ms 610764 KB Output is correct
57 Correct 253 ms 610868 KB Output is correct
58 Correct 254 ms 610880 KB Output is correct
59 Correct 260 ms 610860 KB Output is correct
60 Correct 252 ms 610872 KB Output is correct
61 Correct 254 ms 610868 KB Output is correct
62 Correct 257 ms 610880 KB Output is correct
63 Correct 268 ms 610776 KB Output is correct
64 Correct 259 ms 610880 KB Output is correct
65 Correct 255 ms 610796 KB Output is correct
66 Correct 264 ms 610880 KB Output is correct
67 Correct 264 ms 610876 KB Output is correct
68 Correct 269 ms 610904 KB Output is correct
69 Correct 267 ms 610892 KB Output is correct
70 Correct 267 ms 610892 KB Output is correct
71 Correct 261 ms 610748 KB Output is correct
72 Correct 254 ms 610876 KB Output is correct
73 Correct 256 ms 610820 KB Output is correct
74 Correct 255 ms 610760 KB Output is correct
75 Correct 259 ms 610836 KB Output is correct
76 Correct 261 ms 610824 KB Output is correct
77 Correct 273 ms 610816 KB Output is correct
78 Correct 253 ms 610740 KB Output is correct
79 Correct 255 ms 610868 KB Output is correct
80 Correct 258 ms 610912 KB Output is correct
81 Correct 255 ms 610828 KB Output is correct
82 Correct 264 ms 610788 KB Output is correct
83 Correct 259 ms 610780 KB Output is correct
84 Correct 249 ms 610876 KB Output is correct
85 Correct 250 ms 610768 KB Output is correct
86 Correct 253 ms 610880 KB Output is correct
87 Correct 262 ms 610868 KB Output is correct
88 Correct 258 ms 610860 KB Output is correct
89 Correct 253 ms 611036 KB Output is correct
90 Correct 250 ms 610864 KB Output is correct
91 Correct 250 ms 610792 KB Output is correct
92 Correct 255 ms 610828 KB Output is correct
93 Correct 251 ms 610880 KB Output is correct
94 Correct 248 ms 610776 KB Output is correct
95 Correct 261 ms 610864 KB Output is correct
96 Correct 250 ms 610876 KB Output is correct
97 Correct 251 ms 610792 KB Output is correct
98 Correct 250 ms 610736 KB Output is correct
99 Correct 251 ms 610768 KB Output is correct
100 Correct 268 ms 610824 KB Output is correct
101 Correct 263 ms 610764 KB Output is correct
102 Correct 252 ms 610828 KB Output is correct
103 Correct 252 ms 610800 KB Output is correct
104 Correct 255 ms 610796 KB Output is correct
105 Correct 249 ms 610876 KB Output is correct
106 Correct 248 ms 610788 KB Output is correct
107 Correct 257 ms 610880 KB Output is correct
108 Correct 265 ms 610780 KB Output is correct
109 Correct 353 ms 610836 KB Output is correct
110 Correct 271 ms 611380 KB Output is correct
111 Correct 260 ms 611920 KB Output is correct
112 Correct 256 ms 611788 KB Output is correct
113 Correct 271 ms 611716 KB Output is correct
114 Correct 256 ms 611656 KB Output is correct
115 Correct 258 ms 611576 KB Output is correct
116 Correct 265 ms 611728 KB Output is correct
117 Correct 263 ms 611652 KB Output is correct
118 Correct 256 ms 611540 KB Output is correct
119 Correct 289 ms 613580 KB Output is correct
120 Correct 268 ms 613020 KB Output is correct
121 Correct 429 ms 613472 KB Output is correct
122 Correct 261 ms 612812 KB Output is correct
123 Correct 252 ms 612796 KB Output is correct
124 Correct 334 ms 620452 KB Output is correct
125 Correct 480 ms 638268 KB Output is correct
126 Correct 347 ms 636236 KB Output is correct
127 Execution timed out 2094 ms 637388 KB Time limit exceeded
128 Halted 0 ms 0 KB -