oj.uz

Submission #948932

# Submission time Handle Problem Language Result Execution time Memory
948932 2024-03-18T16:42:02 Z Nhoksocqt1 Mars (APIO22_mars) C++17
21 / 100
 95 ms 13120 KB 
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 22;
const int lx[] = {-1, 0, 0, 1}, ly[] = {0, -1, 1, 0};

vector<ii> B[MAXN][2 * MAXN][2 * MAXN];
int sz[MAXN][2 * MAXN][2 * MAXN];
bool dx[2 * MAXN][2 * MAXN], dxc[MAXN][2 * MAXN][2 * MAXN][3][3];

void bfs_mark(int x, int y, int n) {
    queue<ii> qu;
    qu.push(ii(x, y));
    dx[x][y] = 1;

    while(sz(qu)) {
        int x(qu.front().fi), y(qu.front().se);
        qu.pop();

        for (int id = 0; id < 4; ++id) {
            int u(x + lx[id]), v(y + ly[id]);
            if(min(u, v) < 0 || max(u, v) > 2 * n || dx[u][v])
                continue;

            dx[u][v] = 1;
            qu.push(ii(u, v));
        }
    }
}

void init(int n, int maxk) {
    for (int i = 0; i <= 2 * n; ++i) {
        for (int j = 0; j <= 2 * n; ++j) {
            for (int k = 0; k <= maxk + 1; ++k) {
                sz[k][i][j] = 0;
                for (int lx = 0; lx < 3; ++lx) {
                    for (int ly = 0; ly < 3; ++ly)
                        dxc[k][i][j][lx][ly] = 0;
                }

                B[k][i][j].clear();
            }

            B[0][i][j].push_back(ii(i, j));
            sz[0][i][j] = 1;
        }
    }

    for (int k = 0; k <= maxk; ++k) {
        for (int i = 0; i + 2 * k <= 2 * n; ++i) {
            for (int j = 0; j + 2 * k <= 2 * n; ++j) {
                int minSz(1e9), u(-1), v(-1);
                for (int lx = 0; lx < 3; ++lx) {
                    for (int ly = 0; ly < 3; ++ly) {
                        int ni(i - lx), nj(j - ly);
                        if(min(ni, nj) >= 0 && max(ni, nj) <= 2 * (n - k - 1) && minSz > sz[k + 1][ni][nj]) {
                            minSz = sz[k + 1][ni][nj];
                            u = ni, v = nj;
                        }
                    }
                }

                dxc[k + 1][u][v][i - u][j - v] = 1;
                sz[k + 1][u][v] += sz[k][i][j];
                //cout << '.' << u << ' ' << v << ' ' << i << ' ' << j << '\n';
            }
        }

        if(maxk + 1 < n)
            continue;

        for (int i = 0; i + 2 * (k + 1) <= 2 * n; ++i) {
            for (int j = 0; j + 2 * (k + 1) <= 2 * n; ++j) {
                for (int lx = 0; lx < 3; ++lx) {
                    for (int ly = 0; ly < 3; ++ly) {
                        int ni(i + lx), nj(j + ly);
                        if(dxc[k + 1][i][j][lx][ly]) {
                            for (int it = 0; it < sz(B[k][ni][nj]); ++it)
                                B[k + 1][i][j].push_back(B[k][ni][nj][it]);
                        }
                    }
                }
            }
        }
    }
}

string process(vector<vector<string>> str, int i, int j, int k, int n) {
    init(n, k);

    string res;
    for (int lx = 0; lx < 3; ++lx) {
        for (int ly = 0; ly < 3; ++ly) {
            if(dxc[k + 1][i][j][lx][ly]) {
                string s(str[lx][ly]);
                int szn = sz[k][i + lx][j + ly];
                while(sz(s) > szn)
                    s.pop_back();

                res += s;
            }
        }
    }

    if(k + 1 == n) {
        for (int it = 0; it < sz(B[n][0][0]); ++it) {
            int x(B[n][0][0][it].fi), y(B[n][0][0][it].se);
            dx[x][y] = (res[it] == '0');
        }

        /*for (int i = 0; i <= 2 * n; ++i) {
            for (int j = 0; j <= 2 * n; ++j)
                cout << dx[i][j] << " \n"[j == 2 * n];
        }*/

        int cnt_islands(0);
        for (int i = 0; i <= 2 * n; ++i) {
            for (int j = 0; j <= 2 * n; ++j) {
                if(!dx[i][j]) {
                    bfs_mark(i, j, n);
                    ++cnt_islands;
                }
            }
        }

        string ans;
        while(cnt_islands > 0) {
            ans.push_back(cnt_islands % 2 + '0');
            cnt_islands /= 2;
        }

        if(sz(ans) < 100)
            ans.insert(sz(ans), 100 - sz(ans), '0');

        return ans;
    }

    if(sz(res) < 100)
        res.insert(sz(res), 100 - sz(res), '0');

    return res;
}

#ifdef Nhoksocqt1

int main(void) {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    #define TASK "mars"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    vector<vector<int>> A;
    int n;
    cin >> n;

    for (int i = 0; i < 2 * n + 1; ++i) {
        vector<int> p;
        for (int j = 0; j < 2 * n + 1; ++j) {
            int z;
            cin >> z;
            p.push_back(z);
        }

        A.push_back(p);
    }

    string new_h[2 * MAXN][2 * MAXN], h[2 * MAXN][2 * MAXN];
    for (int i = 0; i < 2 * n + 1; ++i) {
        for (int j = 0; j < 2 * n + 1; ++j) {
            h[i][j] = A[i][j] + '0';
            h[i][j].insert(1, 99, '0');
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int x = 0; x + 2 * (i + 1) <= 2 * n; ++x) {
            for (int y = 0; y + 2 * (i + 1) <= 2 * n; ++y) {
                vector<vector<string>> p;
                for (int lx = 0; lx < 3; ++lx) {
                    vector<string> pt;
                    for (int ly = 0; ly < 3; ++ly)
                        pt.push_back(h[x + lx][y + ly]);

                    p.push_back(pt);
                }

                new_h[x][y] = process(p, x, y, i, n);
                cout << x << ' ' << y << ": " << new_h[x][y] << '\n';
            }
        }

        for (int x = 0; x <= 2 * n; ++x) {
            for (int y = 0; y <= 2 * n; ++y)
                h[x][y] = new_h[x][y];
        }
    }

    cout << "ANSWER: " << h[0][0] << '\n';

    int res(0);
    for (int it = 0; it < 30; ++it)
        res += (1LL << it) * (h[0][0][it] == '1');

    cout << "NUM ISLAND: " << res << '\n';

    return 0;
}

#endif // Nhoksocqt1

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11976 KB Output is correct
2 Correct 8 ms 12364 KB Output is correct
3 Correct 8 ms 12160 KB Output is correct
4 Correct 9 ms 12112 KB Output is correct
5 Correct 8 ms 12076 KB Output is correct
6 Correct 9 ms 12292 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11976 KB Output is correct
2 Correct 8 ms 12364 KB Output is correct
3 Correct 8 ms 12160 KB Output is correct
4 Correct 9 ms 12112 KB Output is correct
5 Correct 8 ms 12076 KB Output is correct
6 Correct 9 ms 12292 KB Output is correct
7 Correct 16 ms 12352 KB Output is correct
8 Correct 16 ms 12492 KB Output is correct
9 Correct 17 ms 12844 KB Output is correct
10 Correct 18 ms 12724 KB Output is correct
11 Correct 20 ms 12812 KB Output is correct
12 Correct 16 ms 12628 KB Output is correct
13 Correct 17 ms 12776 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11976 KB Output is correct
2 Correct 8 ms 12364 KB Output is correct
3 Correct 8 ms 12160 KB Output is correct
4 Correct 9 ms 12112 KB Output is correct
5 Correct 8 ms 12076 KB Output is correct
6 Correct 9 ms 12292 KB Output is correct
7 Correct 16 ms 12352 KB Output is correct
8 Correct 16 ms 12492 KB Output is correct
9 Correct 17 ms 12844 KB Output is correct
10 Correct 18 ms 12724 KB Output is correct
11 Correct 20 ms 12812 KB Output is correct
12 Correct 16 ms 12628 KB Output is correct
13 Correct 17 ms 12776 KB Output is correct
14 Correct 37 ms 12272 KB Output is correct
15 Correct 55 ms 12392 KB Output is correct
16 Correct 55 ms 12268 KB Output is correct
17 Correct 57 ms 12504 KB Output is correct
18 Correct 60 ms 13120 KB Output is correct
19 Correct 52 ms 13024 KB Output is correct
20 Correct 57 ms 12416 KB Output is correct

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11976 KB Output is correct
2 Correct 8 ms 12364 KB Output is correct
3 Correct 8 ms 12160 KB Output is correct
4 Correct 9 ms 12112 KB Output is correct
5 Correct 8 ms 12076 KB Output is correct
6 Correct 9 ms 12292 KB Output is correct
7 Correct 16 ms 12352 KB Output is correct
8 Correct 16 ms 12492 KB Output is correct
9 Correct 17 ms 12844 KB Output is correct
10 Correct 18 ms 12724 KB Output is correct
11 Correct 20 ms 12812 KB Output is correct
12 Correct 16 ms 12628 KB Output is correct
13 Correct 17 ms 12776 KB Output is correct
14 Correct 37 ms 12272 KB Output is correct
15 Correct 55 ms 12392 KB Output is correct
16 Correct 55 ms 12268 KB Output is correct
17 Correct 57 ms 12504 KB Output is correct
18 Correct 60 ms 13120 KB Output is correct
19 Correct 52 ms 13024 KB Output is correct
20 Correct 57 ms 12416 KB Output is correct
21 Correct 95 ms 13116 KB Output is correct
22 Incorrect 20 ms 1828 KB invalid len
23 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11976 KB Output is correct
2 Correct 8 ms 12364 KB Output is correct
3 Correct 8 ms 12160 KB Output is correct
4 Correct 9 ms 12112 KB Output is correct
5 Correct 8 ms 12076 KB Output is correct
6 Correct 9 ms 12292 KB Output is correct
7 Correct 16 ms 12352 KB Output is correct
8 Correct 16 ms 12492 KB Output is correct
9 Correct 17 ms 12844 KB Output is correct
10 Correct 18 ms 12724 KB Output is correct
11 Correct 20 ms 12812 KB Output is correct
12 Correct 16 ms 12628 KB Output is correct
13 Correct 17 ms 12776 KB Output is correct
14 Correct 37 ms 12272 KB Output is correct
15 Correct 55 ms 12392 KB Output is correct
16 Correct 55 ms 12268 KB Output is correct
17 Correct 57 ms 12504 KB Output is correct
18 Correct 60 ms 13120 KB Output is correct
19 Correct 52 ms 13024 KB Output is correct
20 Correct 57 ms 12416 KB Output is correct
21 Correct 95 ms 13116 KB Output is correct
22 Incorrect 20 ms 1828 KB invalid len
23 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11976 KB Output is correct
2 Correct 8 ms 12364 KB Output is correct
3 Correct 8 ms 12160 KB Output is correct
4 Correct 9 ms 12112 KB Output is correct
5 Correct 8 ms 12076 KB Output is correct
6 Correct 9 ms 12292 KB Output is correct
7 Correct 16 ms 12352 KB Output is correct
8 Correct 16 ms 12492 KB Output is correct
9 Correct 17 ms 12844 KB Output is correct
10 Correct 18 ms 12724 KB Output is correct
11 Correct 20 ms 12812 KB Output is correct
12 Correct 16 ms 12628 KB Output is correct
13 Correct 17 ms 12776 KB Output is correct
14 Correct 37 ms 12272 KB Output is correct
15 Correct 55 ms 12392 KB Output is correct
16 Correct 55 ms 12268 KB Output is correct
17 Correct 57 ms 12504 KB Output is correct
18 Correct 60 ms 13120 KB Output is correct
19 Correct 52 ms 13024 KB Output is correct
20 Correct 57 ms 12416 KB Output is correct
21 Correct 95 ms 13116 KB Output is correct
22 Incorrect 20 ms 1828 KB invalid len
23 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11976 KB Output is correct
2 Correct 8 ms 12364 KB Output is correct
3 Correct 8 ms 12160 KB Output is correct
4 Correct 9 ms 12112 KB Output is correct
5 Correct 8 ms 12076 KB Output is correct
6 Correct 9 ms 12292 KB Output is correct
7 Correct 16 ms 12352 KB Output is correct
8 Correct 16 ms 12492 KB Output is correct
9 Correct 17 ms 12844 KB Output is correct
10 Correct 18 ms 12724 KB Output is correct
11 Correct 20 ms 12812 KB Output is correct
12 Correct 16 ms 12628 KB Output is correct
13 Correct 17 ms 12776 KB Output is correct
14 Correct 37 ms 12272 KB Output is correct
15 Correct 55 ms 12392 KB Output is correct
16 Correct 55 ms 12268 KB Output is correct
17 Correct 57 ms 12504 KB Output is correct
18 Correct 60 ms 13120 KB Output is correct
19 Correct 52 ms 13024 KB Output is correct
20 Correct 57 ms 12416 KB Output is correct
21 Correct 95 ms 13116 KB Output is correct
22 Incorrect 20 ms 1828 KB invalid len
23 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11976 KB Output is correct
2 Correct 8 ms 12364 KB Output is correct
3 Correct 8 ms 12160 KB Output is correct
4 Correct 9 ms 12112 KB Output is correct
5 Correct 8 ms 12076 KB Output is correct
6 Correct 9 ms 12292 KB Output is correct
7 Correct 16 ms 12352 KB Output is correct
8 Correct 16 ms 12492 KB Output is correct
9 Correct 17 ms 12844 KB Output is correct
10 Correct 18 ms 12724 KB Output is correct
11 Correct 20 ms 12812 KB Output is correct
12 Correct 16 ms 12628 KB Output is correct
13 Correct 17 ms 12776 KB Output is correct
14 Correct 37 ms 12272 KB Output is correct
15 Correct 55 ms 12392 KB Output is correct
16 Correct 55 ms 12268 KB Output is correct
17 Correct 57 ms 12504 KB Output is correct
18 Correct 60 ms 13120 KB Output is correct
19 Correct 52 ms 13024 KB Output is correct
20 Correct 57 ms 12416 KB Output is correct
21 Correct 95 ms 13116 KB Output is correct
22 Incorrect 20 ms 1828 KB invalid len
23 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11976 KB Output is correct
2 Correct 8 ms 12364 KB Output is correct
3 Correct 8 ms 12160 KB Output is correct
4 Correct 9 ms 12112 KB Output is correct
5 Correct 8 ms 12076 KB Output is correct
6 Correct 9 ms 12292 KB Output is correct
7 Correct 16 ms 12352 KB Output is correct
8 Correct 16 ms 12492 KB Output is correct
9 Correct 17 ms 12844 KB Output is correct
10 Correct 18 ms 12724 KB Output is correct
11 Correct 20 ms 12812 KB Output is correct
12 Correct 16 ms 12628 KB Output is correct
13 Correct 17 ms 12776 KB Output is correct
14 Correct 37 ms 12272 KB Output is correct
15 Correct 55 ms 12392 KB Output is correct
16 Correct 55 ms 12268 KB Output is correct
17 Correct 57 ms 12504 KB Output is correct
18 Correct 60 ms 13120 KB Output is correct
19 Correct 52 ms 13024 KB Output is correct
20 Correct 57 ms 12416 KB Output is correct
21 Correct 95 ms 13116 KB Output is correct
22 Incorrect 20 ms 1828 KB invalid len
23 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11976 KB Output is correct
2 Correct 8 ms 12364 KB Output is correct
3 Correct 8 ms 12160 KB Output is correct
4 Correct 9 ms 12112 KB Output is correct
5 Correct 8 ms 12076 KB Output is correct
6 Correct 9 ms 12292 KB Output is correct
7 Correct 16 ms 12352 KB Output is correct
8 Correct 16 ms 12492 KB Output is correct
9 Correct 17 ms 12844 KB Output is correct
10 Correct 18 ms 12724 KB Output is correct
11 Correct 20 ms 12812 KB Output is correct
12 Correct 16 ms 12628 KB Output is correct
13 Correct 17 ms 12776 KB Output is correct
14 Correct 37 ms 12272 KB Output is correct
15 Correct 55 ms 12392 KB Output is correct
16 Correct 55 ms 12268 KB Output is correct
17 Correct 57 ms 12504 KB Output is correct
18 Correct 60 ms 13120 KB Output is correct
19 Correct 52 ms 13024 KB Output is correct
20 Correct 57 ms 12416 KB Output is correct
21 Correct 95 ms 13116 KB Output is correct
22 Incorrect 20 ms 1828 KB invalid len
23 Halted 0 ms 0 KB -