Submission #932745

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
932745	2024-02-24T06:09:02 Z	maomao90	Mars (APIO22_mars)	C++17	36 / 100	112 ms	4880 KB

mars

// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
#include "mars.h"
using namespace std;

#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 200005;
const int dirr[] = {1, 0, -1, 0}, dirc[] = {0, 1, 0, -1};

string process(vector<vector<string>> a, int i, int j, int k, int n) {
    int tn = 3 + 2 * k;
    vector<string> grid(tn, string(tn, '0'));
    REP (x, 0, 3) {
        REP (y, 0, 3) {
            REP (p, 0, (k + 1) * (k + 1)) {
                int r = x + 2 * (p / (k + 1)),
                    c = y + 2 * (p % (k + 1));
                grid[r][c] = a[x][y][p];
            }
        }
    }
    //cerr << i << ' ' << j << ' ' << k << '\n';
    //REP (r, 0, tn) {
        //cerr << grid[r] << '\n';
    //}
    if (k == n - 1) {
        vector<vector<bool>> vis(tn, vector<bool>(tn, 0));
        int comp = 0;
        REP (r, 0, tn) {
            REP (c, 0, tn) {
                if (vis[r][c] || grid[r][c] == '0') {
                    continue;
                }
                comp++;
                queue<ii> bfs;
                bfs.push({r, c});
                vis[r][c] = 1;
                while (!bfs.empty()) {
                    auto [ur, uc] = bfs.front(); bfs.pop();
                    REP (k, 0, 4) {
                        int vr = ur + dirr[k], vc = uc + dirc[k];
                        if (vr < 0 || vr >= tn || vc < 0 || vc >= tn) {
                            continue;
                        }
                        if (grid[vr][vc] == '0' || vis[vr][vc]) {
                            continue;
                        }
                        bfs.push({vr, vc});
                        vis[vr][vc] = 1;
                    }
                }
            }
        }
        string res(100, '0');
        REP (k, 0, 30) {
            if (comp >> k & 1) {
                res[k] = '1';
            }
        }
        return res;
    }
    string res;
    for (int r = 0; r < tn; r += 2) {
        for (int c = 0; c < tn; c += 2) {
            res += grid[r][c];
        }
    }
    res.resize(100, '0');
    return res;
}

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3800 KB	Output is correct
2	Correct	6 ms	3452 KB	Output is correct
3	Correct	7 ms	3700 KB	Output is correct
4	Correct	7 ms	3636 KB	Output is correct
5	Correct	5 ms	3624 KB	Output is correct
6	Correct	2 ms	3792 KB	Output is correct

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3800 KB	Output is correct
2	Correct	6 ms	3452 KB	Output is correct
3	Correct	7 ms	3700 KB	Output is correct
4	Correct	7 ms	3636 KB	Output is correct
5	Correct	5 ms	3624 KB	Output is correct
6	Correct	2 ms	3792 KB	Output is correct
7	Correct	8 ms	3824 KB	Output is correct
8	Correct	8 ms	3876 KB	Output is correct
9	Correct	8 ms	3960 KB	Output is correct
10	Correct	8 ms	3584 KB	Output is correct
11	Correct	8 ms	3720 KB	Output is correct
12	Correct	8 ms	3872 KB	Output is correct
13	Correct	8 ms	3712 KB	Output is correct

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3800 KB	Output is correct
2	Correct	6 ms	3452 KB	Output is correct
3	Correct	7 ms	3700 KB	Output is correct
4	Correct	7 ms	3636 KB	Output is correct
5	Correct	5 ms	3624 KB	Output is correct
6	Correct	2 ms	3792 KB	Output is correct
7	Correct	8 ms	3824 KB	Output is correct
8	Correct	8 ms	3876 KB	Output is correct
9	Correct	8 ms	3960 KB	Output is correct
10	Correct	8 ms	3584 KB	Output is correct
11	Correct	8 ms	3720 KB	Output is correct
12	Correct	8 ms	3872 KB	Output is correct
13	Correct	8 ms	3712 KB	Output is correct
14	Correct	16 ms	4236 KB	Output is correct
15	Correct	28 ms	4692 KB	Output is correct
16	Correct	24 ms	4084 KB	Output is correct
17	Correct	23 ms	4208 KB	Output is correct
18	Correct	24 ms	4268 KB	Output is correct
19	Correct	26 ms	3836 KB	Output is correct
20	Correct	23 ms	4284 KB	Output is correct

Subtask #4
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3800 KB	Output is correct
2	Correct	6 ms	3452 KB	Output is correct
3	Correct	7 ms	3700 KB	Output is correct
4	Correct	7 ms	3636 KB	Output is correct
5	Correct	5 ms	3624 KB	Output is correct
6	Correct	2 ms	3792 KB	Output is correct
7	Correct	8 ms	3824 KB	Output is correct
8	Correct	8 ms	3876 KB	Output is correct
9	Correct	8 ms	3960 KB	Output is correct
10	Correct	8 ms	3584 KB	Output is correct
11	Correct	8 ms	3720 KB	Output is correct
12	Correct	8 ms	3872 KB	Output is correct
13	Correct	8 ms	3712 KB	Output is correct
14	Correct	16 ms	4236 KB	Output is correct
15	Correct	28 ms	4692 KB	Output is correct
16	Correct	24 ms	4084 KB	Output is correct
17	Correct	23 ms	4208 KB	Output is correct
18	Correct	24 ms	4268 KB	Output is correct
19	Correct	26 ms	3836 KB	Output is correct
20	Correct	23 ms	4284 KB	Output is correct
21	Correct	38 ms	4556 KB	Output is correct
22	Correct	56 ms	4676 KB	Output is correct
23	Correct	51 ms	4332 KB	Output is correct
24	Correct	51 ms	4120 KB	Output is correct
25	Correct	56 ms	4532 KB	Output is correct
26	Correct	53 ms	4244 KB	Output is correct
27	Correct	57 ms	4880 KB	Output is correct
28	Correct	58 ms	4628 KB	Output is correct

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3800 KB	Output is correct
2	Correct	6 ms	3452 KB	Output is correct
3	Correct	7 ms	3700 KB	Output is correct
4	Correct	7 ms	3636 KB	Output is correct
5	Correct	5 ms	3624 KB	Output is correct
6	Correct	2 ms	3792 KB	Output is correct
7	Correct	8 ms	3824 KB	Output is correct
8	Correct	8 ms	3876 KB	Output is correct
9	Correct	8 ms	3960 KB	Output is correct
10	Correct	8 ms	3584 KB	Output is correct
11	Correct	8 ms	3720 KB	Output is correct
12	Correct	8 ms	3872 KB	Output is correct
13	Correct	8 ms	3712 KB	Output is correct
14	Correct	16 ms	4236 KB	Output is correct
15	Correct	28 ms	4692 KB	Output is correct
16	Correct	24 ms	4084 KB	Output is correct
17	Correct	23 ms	4208 KB	Output is correct
18	Correct	24 ms	4268 KB	Output is correct
19	Correct	26 ms	3836 KB	Output is correct
20	Correct	23 ms	4284 KB	Output is correct
21	Correct	38 ms	4556 KB	Output is correct
22	Correct	56 ms	4676 KB	Output is correct
23	Correct	51 ms	4332 KB	Output is correct
24	Correct	51 ms	4120 KB	Output is correct
25	Correct	56 ms	4532 KB	Output is correct
26	Correct	53 ms	4244 KB	Output is correct
27	Correct	57 ms	4880 KB	Output is correct
28	Correct	58 ms	4628 KB	Output is correct
29	Correct	74 ms	4684 KB	Output is correct
30	Correct	105 ms	4776 KB	Output is correct
31	Correct	106 ms	4464 KB	Output is correct
32	Correct	109 ms	4664 KB	Output is correct
33	Correct	105 ms	4452 KB	Output is correct
34	Correct	107 ms	4060 KB	Output is correct
35	Correct	112 ms	4164 KB	Output is correct
36	Correct	104 ms	4372 KB	Output is correct

Subtask #6
0.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3800 KB	Output is correct
2	Correct	6 ms	3452 KB	Output is correct
3	Correct	7 ms	3700 KB	Output is correct
4	Correct	7 ms	3636 KB	Output is correct
5	Correct	5 ms	3624 KB	Output is correct
6	Correct	2 ms	3792 KB	Output is correct
7	Correct	8 ms	3824 KB	Output is correct
8	Correct	8 ms	3876 KB	Output is correct
9	Correct	8 ms	3960 KB	Output is correct
10	Correct	8 ms	3584 KB	Output is correct
11	Correct	8 ms	3720 KB	Output is correct
12	Correct	8 ms	3872 KB	Output is correct
13	Correct	8 ms	3712 KB	Output is correct
14	Correct	16 ms	4236 KB	Output is correct
15	Correct	28 ms	4692 KB	Output is correct
16	Correct	24 ms	4084 KB	Output is correct
17	Correct	23 ms	4208 KB	Output is correct
18	Correct	24 ms	4268 KB	Output is correct
19	Correct	26 ms	3836 KB	Output is correct
20	Correct	23 ms	4284 KB	Output is correct
21	Correct	38 ms	4556 KB	Output is correct
22	Correct	56 ms	4676 KB	Output is correct
23	Correct	51 ms	4332 KB	Output is correct
24	Correct	51 ms	4120 KB	Output is correct
25	Correct	56 ms	4532 KB	Output is correct
26	Correct	53 ms	4244 KB	Output is correct
27	Correct	57 ms	4880 KB	Output is correct
28	Correct	58 ms	4628 KB	Output is correct
29	Correct	74 ms	4684 KB	Output is correct
30	Correct	105 ms	4776 KB	Output is correct
31	Correct	106 ms	4464 KB	Output is correct
32	Correct	109 ms	4664 KB	Output is correct
33	Correct	105 ms	4452 KB	Output is correct
34	Correct	107 ms	4060 KB	Output is correct
35	Correct	112 ms	4164 KB	Output is correct
36	Correct	104 ms	4372 KB	Output is correct
37	Incorrect	21 ms	748 KB	Incorrect
38	Halted	0 ms	0 KB	-

Subtask #7
0.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3800 KB	Output is correct
2	Correct	6 ms	3452 KB	Output is correct
3	Correct	7 ms	3700 KB	Output is correct
4	Correct	7 ms	3636 KB	Output is correct
5	Correct	5 ms	3624 KB	Output is correct
6	Correct	2 ms	3792 KB	Output is correct
7	Correct	8 ms	3824 KB	Output is correct
8	Correct	8 ms	3876 KB	Output is correct
9	Correct	8 ms	3960 KB	Output is correct
10	Correct	8 ms	3584 KB	Output is correct
11	Correct	8 ms	3720 KB	Output is correct
12	Correct	8 ms	3872 KB	Output is correct
13	Correct	8 ms	3712 KB	Output is correct
14	Correct	16 ms	4236 KB	Output is correct
15	Correct	28 ms	4692 KB	Output is correct
16	Correct	24 ms	4084 KB	Output is correct
17	Correct	23 ms	4208 KB	Output is correct
18	Correct	24 ms	4268 KB	Output is correct
19	Correct	26 ms	3836 KB	Output is correct
20	Correct	23 ms	4284 KB	Output is correct
21	Correct	38 ms	4556 KB	Output is correct
22	Correct	56 ms	4676 KB	Output is correct
23	Correct	51 ms	4332 KB	Output is correct
24	Correct	51 ms	4120 KB	Output is correct
25	Correct	56 ms	4532 KB	Output is correct
26	Correct	53 ms	4244 KB	Output is correct
27	Correct	57 ms	4880 KB	Output is correct
28	Correct	58 ms	4628 KB	Output is correct
29	Correct	74 ms	4684 KB	Output is correct
30	Correct	105 ms	4776 KB	Output is correct
31	Correct	106 ms	4464 KB	Output is correct
32	Correct	109 ms	4664 KB	Output is correct
33	Correct	105 ms	4452 KB	Output is correct
34	Correct	107 ms	4060 KB	Output is correct
35	Correct	112 ms	4164 KB	Output is correct
36	Correct	104 ms	4372 KB	Output is correct
37	Incorrect	21 ms	748 KB	Incorrect
38	Halted	0 ms	0 KB	-

Subtask #8
0.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3800 KB	Output is correct
2	Correct	6 ms	3452 KB	Output is correct
3	Correct	7 ms	3700 KB	Output is correct
4	Correct	7 ms	3636 KB	Output is correct
5	Correct	5 ms	3624 KB	Output is correct
6	Correct	2 ms	3792 KB	Output is correct
7	Correct	8 ms	3824 KB	Output is correct
8	Correct	8 ms	3876 KB	Output is correct
9	Correct	8 ms	3960 KB	Output is correct
10	Correct	8 ms	3584 KB	Output is correct
11	Correct	8 ms	3720 KB	Output is correct
12	Correct	8 ms	3872 KB	Output is correct
13	Correct	8 ms	3712 KB	Output is correct
14	Correct	16 ms	4236 KB	Output is correct
15	Correct	28 ms	4692 KB	Output is correct
16	Correct	24 ms	4084 KB	Output is correct
17	Correct	23 ms	4208 KB	Output is correct
18	Correct	24 ms	4268 KB	Output is correct
19	Correct	26 ms	3836 KB	Output is correct
20	Correct	23 ms	4284 KB	Output is correct
21	Correct	38 ms	4556 KB	Output is correct
22	Correct	56 ms	4676 KB	Output is correct
23	Correct	51 ms	4332 KB	Output is correct
24	Correct	51 ms	4120 KB	Output is correct
25	Correct	56 ms	4532 KB	Output is correct
26	Correct	53 ms	4244 KB	Output is correct
27	Correct	57 ms	4880 KB	Output is correct
28	Correct	58 ms	4628 KB	Output is correct
29	Correct	74 ms	4684 KB	Output is correct
30	Correct	105 ms	4776 KB	Output is correct
31	Correct	106 ms	4464 KB	Output is correct
32	Correct	109 ms	4664 KB	Output is correct
33	Correct	105 ms	4452 KB	Output is correct
34	Correct	107 ms	4060 KB	Output is correct
35	Correct	112 ms	4164 KB	Output is correct
36	Correct	104 ms	4372 KB	Output is correct
37	Incorrect	21 ms	748 KB	Incorrect
38	Halted	0 ms	0 KB	-

Subtask #9
0.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3800 KB	Output is correct
2	Correct	6 ms	3452 KB	Output is correct
3	Correct	7 ms	3700 KB	Output is correct
4	Correct	7 ms	3636 KB	Output is correct
5	Correct	5 ms	3624 KB	Output is correct
6	Correct	2 ms	3792 KB	Output is correct
7	Correct	8 ms	3824 KB	Output is correct
8	Correct	8 ms	3876 KB	Output is correct
9	Correct	8 ms	3960 KB	Output is correct
10	Correct	8 ms	3584 KB	Output is correct
11	Correct	8 ms	3720 KB	Output is correct
12	Correct	8 ms	3872 KB	Output is correct
13	Correct	8 ms	3712 KB	Output is correct
14	Correct	16 ms	4236 KB	Output is correct
15	Correct	28 ms	4692 KB	Output is correct
16	Correct	24 ms	4084 KB	Output is correct
17	Correct	23 ms	4208 KB	Output is correct
18	Correct	24 ms	4268 KB	Output is correct
19	Correct	26 ms	3836 KB	Output is correct
20	Correct	23 ms	4284 KB	Output is correct
21	Correct	38 ms	4556 KB	Output is correct
22	Correct	56 ms	4676 KB	Output is correct
23	Correct	51 ms	4332 KB	Output is correct
24	Correct	51 ms	4120 KB	Output is correct
25	Correct	56 ms	4532 KB	Output is correct
26	Correct	53 ms	4244 KB	Output is correct
27	Correct	57 ms	4880 KB	Output is correct
28	Correct	58 ms	4628 KB	Output is correct
29	Correct	74 ms	4684 KB	Output is correct
30	Correct	105 ms	4776 KB	Output is correct
31	Correct	106 ms	4464 KB	Output is correct
32	Correct	109 ms	4664 KB	Output is correct
33	Correct	105 ms	4452 KB	Output is correct
34	Correct	107 ms	4060 KB	Output is correct
35	Correct	112 ms	4164 KB	Output is correct
36	Correct	104 ms	4372 KB	Output is correct
37	Incorrect	21 ms	748 KB	Incorrect
38	Halted	0 ms	0 KB	-

Subtask #10
0.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3800 KB	Output is correct
2	Correct	6 ms	3452 KB	Output is correct
3	Correct	7 ms	3700 KB	Output is correct
4	Correct	7 ms	3636 KB	Output is correct
5	Correct	5 ms	3624 KB	Output is correct
6	Correct	2 ms	3792 KB	Output is correct
7	Correct	8 ms	3824 KB	Output is correct
8	Correct	8 ms	3876 KB	Output is correct
9	Correct	8 ms	3960 KB	Output is correct
10	Correct	8 ms	3584 KB	Output is correct
11	Correct	8 ms	3720 KB	Output is correct
12	Correct	8 ms	3872 KB	Output is correct
13	Correct	8 ms	3712 KB	Output is correct
14	Correct	16 ms	4236 KB	Output is correct
15	Correct	28 ms	4692 KB	Output is correct
16	Correct	24 ms	4084 KB	Output is correct
17	Correct	23 ms	4208 KB	Output is correct
18	Correct	24 ms	4268 KB	Output is correct
19	Correct	26 ms	3836 KB	Output is correct
20	Correct	23 ms	4284 KB	Output is correct
21	Correct	38 ms	4556 KB	Output is correct
22	Correct	56 ms	4676 KB	Output is correct
23	Correct	51 ms	4332 KB	Output is correct
24	Correct	51 ms	4120 KB	Output is correct
25	Correct	56 ms	4532 KB	Output is correct
26	Correct	53 ms	4244 KB	Output is correct
27	Correct	57 ms	4880 KB	Output is correct
28	Correct	58 ms	4628 KB	Output is correct
29	Correct	74 ms	4684 KB	Output is correct
30	Correct	105 ms	4776 KB	Output is correct
31	Correct	106 ms	4464 KB	Output is correct
32	Correct	109 ms	4664 KB	Output is correct
33	Correct	105 ms	4452 KB	Output is correct
34	Correct	107 ms	4060 KB	Output is correct
35	Correct	112 ms	4164 KB	Output is correct
36	Correct	104 ms	4372 KB	Output is correct
37	Incorrect	21 ms	748 KB	Incorrect
38	Halted	0 ms	0 KB	-

Submission #932745

Compilation message