Submission #731109

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
731109	2023-04-27T03:03:40 Z	hoainiem	Mars (APIO22_mars)	C++17	29 / 100	138 ms	2780 KB

mars

#include "mars.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
int get(int i, int j, int n){
    i /= 2;
    j /= 2;
    n = n / 2 + (n & 1);
    return i * n + j;
}
string operator|(string x, string y){
    for (int i = 0; i < 100; i++)
        if (y[i] == '1')
            x[i] = y[i];
    return x;
}
std::string process(std::vector <std::vector<std::string>> a, int x, int y, int k, int n){
    if (!k)
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                if (a[i][j][0] == '1'){
                    a[i][j][0] = '0';
                    a[i][j][get(x + i, y + j, n * 2 + 1)] = '1';
                }
    a[0][0] = a[0][0] | a[2][0] | a[0][2] | a[2][2];
    if (k < n - 1)
        return a[0][0];
    n = n * 2 + 1;
    a[0][1] = a[0][1] | a[2][1];
    a[1][0] = a[1][0] | a[1][2];
    bitset<48>land[48];
    int h1[4]{1, -1, 0, 0};
    int h2[4]{0, 0, 1, -1};
    bool vis[48][48];
    for (int i = 0; i < n; i++)
        land[i].reset();
    for (x = 0; x < 2; x++)
        for (int y = 0; y < 2; y++)
            for (int i = x; i < n; i += 2)
                for (int j = y; j < n; j += 2)
                    if (a[x][y][get(i, j, n)] == '1')
                        land[i].set(j);
    memset(vis, false, sizeof(vis));
    queue<pii>s;
    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (!vis[i][j] && land[i].test(j)){
                ans++;
                s.push({i, j});
                vis[i][j] = true;
                while (!s.empty()){
                    pii u = s.front();
                    s.pop();
                    for (int c = 0; c < 4; c++){
                        pii v = {u.fi + h1[c], u.se + h2[c]};
                        if (v.fi < 0 || v.fi >= n || v.se < 0 || v.se >= n || !land[v.fi].test(v.se) || vis[v.fi][v.se])
                            continue;
                        s.push(v);
                        vis[v.fi][v.se] = true;
                    }
                }
            }
    string res;
    res.resize(100, '0');
    for (int i = 0; i < 15; i++)
        if ((ans >> i) & 1)
            res[i] = '1';
    return res;
}

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1708 KB	Output is correct
2	Correct	8 ms	1948 KB	Output is correct
3	Correct	8 ms	2168 KB	Output is correct
4	Correct	8 ms	2140 KB	Output is correct
5	Correct	8 ms	2020 KB	Output is correct
6	Correct	8 ms	2216 KB	Output is correct

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1708 KB	Output is correct
2	Correct	8 ms	1948 KB	Output is correct
3	Correct	8 ms	2168 KB	Output is correct
4	Correct	8 ms	2140 KB	Output is correct
5	Correct	8 ms	2020 KB	Output is correct
6	Correct	8 ms	2216 KB	Output is correct
7	Correct	12 ms	2036 KB	Output is correct
8	Correct	16 ms	1864 KB	Output is correct
9	Correct	19 ms	2192 KB	Output is correct
10	Correct	17 ms	2048 KB	Output is correct
11	Correct	18 ms	2064 KB	Output is correct
12	Correct	17 ms	1824 KB	Output is correct
13	Correct	16 ms	2176 KB	Output is correct

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1708 KB	Output is correct
2	Correct	8 ms	1948 KB	Output is correct
3	Correct	8 ms	2168 KB	Output is correct
4	Correct	8 ms	2140 KB	Output is correct
5	Correct	8 ms	2020 KB	Output is correct
6	Correct	8 ms	2216 KB	Output is correct
7	Correct	12 ms	2036 KB	Output is correct
8	Correct	16 ms	1864 KB	Output is correct
9	Correct	19 ms	2192 KB	Output is correct
10	Correct	17 ms	2048 KB	Output is correct
11	Correct	18 ms	2064 KB	Output is correct
12	Correct	17 ms	1824 KB	Output is correct
13	Correct	16 ms	2176 KB	Output is correct
14	Correct	34 ms	2376 KB	Output is correct
15	Correct	45 ms	2456 KB	Output is correct
16	Correct	46 ms	2596 KB	Output is correct
17	Correct	46 ms	2460 KB	Output is correct
18	Correct	41 ms	2532 KB	Output is correct
19	Correct	51 ms	2528 KB	Output is correct
20	Correct	41 ms	2492 KB	Output is correct

Subtask #4
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1708 KB	Output is correct
2	Correct	8 ms	1948 KB	Output is correct
3	Correct	8 ms	2168 KB	Output is correct
4	Correct	8 ms	2140 KB	Output is correct
5	Correct	8 ms	2020 KB	Output is correct
6	Correct	8 ms	2216 KB	Output is correct
7	Correct	12 ms	2036 KB	Output is correct
8	Correct	16 ms	1864 KB	Output is correct
9	Correct	19 ms	2192 KB	Output is correct
10	Correct	17 ms	2048 KB	Output is correct
11	Correct	18 ms	2064 KB	Output is correct
12	Correct	17 ms	1824 KB	Output is correct
13	Correct	16 ms	2176 KB	Output is correct
14	Correct	34 ms	2376 KB	Output is correct
15	Correct	45 ms	2456 KB	Output is correct
16	Correct	46 ms	2596 KB	Output is correct
17	Correct	46 ms	2460 KB	Output is correct
18	Correct	41 ms	2532 KB	Output is correct
19	Correct	51 ms	2528 KB	Output is correct
20	Correct	41 ms	2492 KB	Output is correct
21	Correct	65 ms	2608 KB	Output is correct
22	Correct	98 ms	2604 KB	Output is correct
23	Correct	93 ms	2736 KB	Output is correct
24	Correct	95 ms	2744 KB	Output is correct
25	Correct	91 ms	2680 KB	Output is correct
26	Correct	99 ms	2780 KB	Output is correct
27	Correct	90 ms	2652 KB	Output is correct
28	Correct	94 ms	2772 KB	Output is correct

Subtask #5
0.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1708 KB	Output is correct
2	Correct	8 ms	1948 KB	Output is correct
3	Correct	8 ms	2168 KB	Output is correct
4	Correct	8 ms	2140 KB	Output is correct
5	Correct	8 ms	2020 KB	Output is correct
6	Correct	8 ms	2216 KB	Output is correct
7	Correct	12 ms	2036 KB	Output is correct
8	Correct	16 ms	1864 KB	Output is correct
9	Correct	19 ms	2192 KB	Output is correct
10	Correct	17 ms	2048 KB	Output is correct
11	Correct	18 ms	2064 KB	Output is correct
12	Correct	17 ms	1824 KB	Output is correct
13	Correct	16 ms	2176 KB	Output is correct
14	Correct	34 ms	2376 KB	Output is correct
15	Correct	45 ms	2456 KB	Output is correct
16	Correct	46 ms	2596 KB	Output is correct
17	Correct	46 ms	2460 KB	Output is correct
18	Correct	41 ms	2532 KB	Output is correct
19	Correct	51 ms	2528 KB	Output is correct
20	Correct	41 ms	2492 KB	Output is correct
21	Correct	65 ms	2608 KB	Output is correct
22	Correct	98 ms	2604 KB	Output is correct
23	Correct	93 ms	2736 KB	Output is correct
24	Correct	95 ms	2744 KB	Output is correct
25	Correct	91 ms	2680 KB	Output is correct
26	Correct	99 ms	2780 KB	Output is correct
27	Correct	90 ms	2652 KB	Output is correct
28	Correct	94 ms	2772 KB	Output is correct
29	Correct	138 ms	2712 KB	Output is correct
30	Runtime error	6 ms	500 KB	Execution killed with signal 6
31	Halted	0 ms	0 KB	-

Subtask #6
0.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1708 KB	Output is correct
2	Correct	8 ms	1948 KB	Output is correct
3	Correct	8 ms	2168 KB	Output is correct
4	Correct	8 ms	2140 KB	Output is correct
5	Correct	8 ms	2020 KB	Output is correct
6	Correct	8 ms	2216 KB	Output is correct
7	Correct	12 ms	2036 KB	Output is correct
8	Correct	16 ms	1864 KB	Output is correct
9	Correct	19 ms	2192 KB	Output is correct
10	Correct	17 ms	2048 KB	Output is correct
11	Correct	18 ms	2064 KB	Output is correct
12	Correct	17 ms	1824 KB	Output is correct
13	Correct	16 ms	2176 KB	Output is correct
14	Correct	34 ms	2376 KB	Output is correct
15	Correct	45 ms	2456 KB	Output is correct
16	Correct	46 ms	2596 KB	Output is correct
17	Correct	46 ms	2460 KB	Output is correct
18	Correct	41 ms	2532 KB	Output is correct
19	Correct	51 ms	2528 KB	Output is correct
20	Correct	41 ms	2492 KB	Output is correct
21	Correct	65 ms	2608 KB	Output is correct
22	Correct	98 ms	2604 KB	Output is correct
23	Correct	93 ms	2736 KB	Output is correct
24	Correct	95 ms	2744 KB	Output is correct
25	Correct	91 ms	2680 KB	Output is correct
26	Correct	99 ms	2780 KB	Output is correct
27	Correct	90 ms	2652 KB	Output is correct
28	Correct	94 ms	2772 KB	Output is correct
29	Correct	138 ms	2712 KB	Output is correct
30	Runtime error	6 ms	500 KB	Execution killed with signal 6
31	Halted	0 ms	0 KB	-

Subtask #7
0.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1708 KB	Output is correct
2	Correct	8 ms	1948 KB	Output is correct
3	Correct	8 ms	2168 KB	Output is correct
4	Correct	8 ms	2140 KB	Output is correct
5	Correct	8 ms	2020 KB	Output is correct
6	Correct	8 ms	2216 KB	Output is correct
7	Correct	12 ms	2036 KB	Output is correct
8	Correct	16 ms	1864 KB	Output is correct
9	Correct	19 ms	2192 KB	Output is correct
10	Correct	17 ms	2048 KB	Output is correct
11	Correct	18 ms	2064 KB	Output is correct
12	Correct	17 ms	1824 KB	Output is correct
13	Correct	16 ms	2176 KB	Output is correct
14	Correct	34 ms	2376 KB	Output is correct
15	Correct	45 ms	2456 KB	Output is correct
16	Correct	46 ms	2596 KB	Output is correct
17	Correct	46 ms	2460 KB	Output is correct
18	Correct	41 ms	2532 KB	Output is correct
19	Correct	51 ms	2528 KB	Output is correct
20	Correct	41 ms	2492 KB	Output is correct
21	Correct	65 ms	2608 KB	Output is correct
22	Correct	98 ms	2604 KB	Output is correct
23	Correct	93 ms	2736 KB	Output is correct
24	Correct	95 ms	2744 KB	Output is correct
25	Correct	91 ms	2680 KB	Output is correct
26	Correct	99 ms	2780 KB	Output is correct
27	Correct	90 ms	2652 KB	Output is correct
28	Correct	94 ms	2772 KB	Output is correct
29	Correct	138 ms	2712 KB	Output is correct
30	Runtime error	6 ms	500 KB	Execution killed with signal 6
31	Halted	0 ms	0 KB	-

Subtask #8
0.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1708 KB	Output is correct
2	Correct	8 ms	1948 KB	Output is correct
3	Correct	8 ms	2168 KB	Output is correct
4	Correct	8 ms	2140 KB	Output is correct
5	Correct	8 ms	2020 KB	Output is correct
6	Correct	8 ms	2216 KB	Output is correct
7	Correct	12 ms	2036 KB	Output is correct
8	Correct	16 ms	1864 KB	Output is correct
9	Correct	19 ms	2192 KB	Output is correct
10	Correct	17 ms	2048 KB	Output is correct
11	Correct	18 ms	2064 KB	Output is correct
12	Correct	17 ms	1824 KB	Output is correct
13	Correct	16 ms	2176 KB	Output is correct
14	Correct	34 ms	2376 KB	Output is correct
15	Correct	45 ms	2456 KB	Output is correct
16	Correct	46 ms	2596 KB	Output is correct
17	Correct	46 ms	2460 KB	Output is correct
18	Correct	41 ms	2532 KB	Output is correct
19	Correct	51 ms	2528 KB	Output is correct
20	Correct	41 ms	2492 KB	Output is correct
21	Correct	65 ms	2608 KB	Output is correct
22	Correct	98 ms	2604 KB	Output is correct
23	Correct	93 ms	2736 KB	Output is correct
24	Correct	95 ms	2744 KB	Output is correct
25	Correct	91 ms	2680 KB	Output is correct
26	Correct	99 ms	2780 KB	Output is correct
27	Correct	90 ms	2652 KB	Output is correct
28	Correct	94 ms	2772 KB	Output is correct
29	Correct	138 ms	2712 KB	Output is correct
30	Runtime error	6 ms	500 KB	Execution killed with signal 6
31	Halted	0 ms	0 KB	-

Subtask #9
0.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1708 KB	Output is correct
2	Correct	8 ms	1948 KB	Output is correct
3	Correct	8 ms	2168 KB	Output is correct
4	Correct	8 ms	2140 KB	Output is correct
5	Correct	8 ms	2020 KB	Output is correct
6	Correct	8 ms	2216 KB	Output is correct
7	Correct	12 ms	2036 KB	Output is correct
8	Correct	16 ms	1864 KB	Output is correct
9	Correct	19 ms	2192 KB	Output is correct
10	Correct	17 ms	2048 KB	Output is correct
11	Correct	18 ms	2064 KB	Output is correct
12	Correct	17 ms	1824 KB	Output is correct
13	Correct	16 ms	2176 KB	Output is correct
14	Correct	34 ms	2376 KB	Output is correct
15	Correct	45 ms	2456 KB	Output is correct
16	Correct	46 ms	2596 KB	Output is correct
17	Correct	46 ms	2460 KB	Output is correct
18	Correct	41 ms	2532 KB	Output is correct
19	Correct	51 ms	2528 KB	Output is correct
20	Correct	41 ms	2492 KB	Output is correct
21	Correct	65 ms	2608 KB	Output is correct
22	Correct	98 ms	2604 KB	Output is correct
23	Correct	93 ms	2736 KB	Output is correct
24	Correct	95 ms	2744 KB	Output is correct
25	Correct	91 ms	2680 KB	Output is correct
26	Correct	99 ms	2780 KB	Output is correct
27	Correct	90 ms	2652 KB	Output is correct
28	Correct	94 ms	2772 KB	Output is correct
29	Correct	138 ms	2712 KB	Output is correct
30	Runtime error	6 ms	500 KB	Execution killed with signal 6
31	Halted	0 ms	0 KB	-

Subtask #10
0.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1708 KB	Output is correct
2	Correct	8 ms	1948 KB	Output is correct
3	Correct	8 ms	2168 KB	Output is correct
4	Correct	8 ms	2140 KB	Output is correct
5	Correct	8 ms	2020 KB	Output is correct
6	Correct	8 ms	2216 KB	Output is correct
7	Correct	12 ms	2036 KB	Output is correct
8	Correct	16 ms	1864 KB	Output is correct
9	Correct	19 ms	2192 KB	Output is correct
10	Correct	17 ms	2048 KB	Output is correct
11	Correct	18 ms	2064 KB	Output is correct
12	Correct	17 ms	1824 KB	Output is correct
13	Correct	16 ms	2176 KB	Output is correct
14	Correct	34 ms	2376 KB	Output is correct
15	Correct	45 ms	2456 KB	Output is correct
16	Correct	46 ms	2596 KB	Output is correct
17	Correct	46 ms	2460 KB	Output is correct
18	Correct	41 ms	2532 KB	Output is correct
19	Correct	51 ms	2528 KB	Output is correct
20	Correct	41 ms	2492 KB	Output is correct
21	Correct	65 ms	2608 KB	Output is correct
22	Correct	98 ms	2604 KB	Output is correct
23	Correct	93 ms	2736 KB	Output is correct
24	Correct	95 ms	2744 KB	Output is correct
25	Correct	91 ms	2680 KB	Output is correct
26	Correct	99 ms	2780 KB	Output is correct
27	Correct	90 ms	2652 KB	Output is correct
28	Correct	94 ms	2772 KB	Output is correct
29	Correct	138 ms	2712 KB	Output is correct
30	Runtime error	6 ms	500 KB	Execution killed with signal 6
31	Halted	0 ms	0 KB	-

Submission #731109

Compilation message