oj.uz

Submission #572668

# Submission time Handle Problem Language Result Execution time Memory
572668 2022-06-05T02:25:22 Z tabr Mars (APIO22_mars) C++17
14 / 100
 23 ms 2292 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

struct dsu {
    vector<int> p;
    vector<int> sz;
    int n;

    dsu(int _n) : n(_n) {
        p = vector<int>(n);
        iota(p.begin(), p.end(), 0);
        sz = vector<int>(n, 1);
    }

    inline int get(int x) {
        if (p[x] == x) {
            return x;
        } else {
            return p[x] = get(p[x]);
        }
    }

    inline bool unite(int x, int y) {
        x = get(x);
        y = get(y);
        if (x == y) {
            return false;
        }
        p[x] = y;
        sz[y] += sz[x];
        return true;
    }

    inline bool same(int x, int y) {
        return (get(x) == get(y));
    }

    inline int size(int x) {
        return sz[get(x)];
    }

    inline bool root(int x) {
        return (x == get(x));
    }
};

string count_islands(vector<string> s) {
    int n = (int) s.size();
    dsu uf(n * n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - 1; j++) {
            if (s[i][j] == '1' && s[i][j + 1] == '1') {
                uf.unite(i * n + j, i * n + j + 1);
            }
        }
    }
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n; j++) {
            if (s[i][j] == '1' && s[i + 1][j] == '1') {
                uf.unite(i * n + j, i * n + j + n);
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (s[i][j] == '1' && uf.root(i * n + j)) {
                ans++;
            }
        }
    }
    string res(100, '0');
    for (int i = 0; i < 20; i++) {
        if (ans & (1 << i)) {
            res[i] = '1';
        }
    }
    return res;
}

vector<int> count_groups(int k, int n) {
    if (k == 0) {
        vector<int> g;
        for (int i = 0; i < 3; i++) {
            g.emplace_back((2 * n + 1) * (i + 1) / 3 - (2 * n + 1) * i / 3);
        }
        return g;
    }
    auto g = count_groups(k - 1, n);
    for (int z = 0; z < 2; z++) {
        for (int i = 0; i < 3; i++) {
            if (g[i] > 1) {
                g[i]--;
                break;
            }
        }
    }
    return g;
}

vector<int> move_from(int k, int n) {
    assert(0 <= k && k < n - 1);
    auto g = count_groups(k, n);
    int l = 2 * (n - k) - 1;
    vector<int> c;
    assert(g[0] + g[1] + g[2] == l + 2);
    for (int z = 0; z < 2; z++) {
        for (int i = 0; i < 3; i++) {
            if (g[i] > 1) {
                g[i]--;
                c.emplace_back(i);
                break;
            }
        }
    }
    for (int i = 0; i < 2; i++) {
        c[i] = g[c[i]];
    }
    for (int i = 0; i < l; i++) {
        c.emplace_back(i);
    }
    sort(c.begin(), c.end());
    return c;
}

vector<vector<vector<pair<int, int>>>> original_pos(int k, int n) {
    int l = 2 * (n - k) + 1;
    vector<vector<vector<pair<int, int>>>> res(l, vector<vector<pair<int, int>>>(l));
    if (k == 0) {
        for (int i = 0; i < l; i++) {
            for (int j = 0; j < l; j++) {
                res[i][j].emplace_back(i, j);
            }
        }
        return res;
    }
    // make l x l board from (l + 2) x (l + 2)
    // (x, y) <- (nx, ny) such that c[nx] == x and c[ny] == y
    auto t = original_pos(k - 1, n);
    auto c = move_from(k - 1, n);
    for (int x = 0; x < l; x++) {
        for (int y = 0; y < l; y++) {
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (x == c[x + i] && y == c[y + j]) {
                        for (auto p : t[x + i][y + j]) {
                            res[x][y].emplace_back(p);
                        }
                    }
                }
            }
        }
    }
    return res;
}

string process(vector<vector<string>> a, int x, int y, int k, int n) {
    auto t = original_pos(k, n);
    if (k == n - 1) {
        vector<string> s(2 * n + 1, string(2 * n + 1, '0'));
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                for (int id = 0; id < (int) t[i][j].size(); id++) {
                    s[t[i][j][id].first][t[i][j][id].second] = a[i][j][id];
                }
            }
        }
        debug(s);
        return count_islands(s);
    }
    auto c = move_from(k, n);
    string res;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (x == c[x + i] && y == c[y + j]) {
                res += a[i][j].substr(0, t[x + i][y + j].size());
            }
        }
    }
    assert(res.size() <= 100);
    res += string(100 - res.size(), '0');
    return res;
}

#ifdef tabr
static void WA(string msg) {
    cout << "WA: " << msg << endl;
    exit(0);
}

static long long to_longlong(string s) {
    long long ans = 0;
    for (int i = (int) s.size() - 1; i >= 0; i--)
        ans = (ans * 2) + s[i] - '0';
    return ans;
}

int main() {
    int t;
    assert(scanf("%d", &t) == 1);
    while (t--) {
        int n;
        assert(scanf("%d", &n) == 1);
        vector<vector<char>> s(2 * n + 1, vector<char>(2 * n + 1));
        for (int i = 0; i < 2 * n + 1; i++)
            for (int j = 0; j < 2 * n + 1; j++)
                assert(scanf(" %c", &s[i][j]) == 1);
        vector<vector<string>> h(2 * n + 1, vector<string>(2 * n + 1, string(100, '0')));
        for (int i = 0; i < 2 * n + 1; i++)
            for (int j = 0; j < 2 * n + 1; j++)
                h[i][j][0] = s[i][j];
        vector<vector<string>> subarr(3, vector<string>(3));
        for (int k = 0; k < n; k++) {
            int m = 2 * (n - k - 1);
            for (int i = 0; i <= m; i++) {
                for (int j = 0; j <= m; j++) {
                    for (int y = 0; y < 3; y++) {
                        for (int x = 0; x < 3; x++) {
                            subarr[y][x] = h[i + y][j + x];
                        }
                    }
                    h[i][j] = process(subarr, i, j, k, n);

                    if (h[i][j].size() != 100) WA("Invalid return length");
                    for (int l = 0; l < 100; l++)
                        if (h[i][j][l] != '0' && h[i][j][l] != '1') WA("Invalid return");
                }
            }
        }
        printf("%lld\n", to_longlong(h[0][0]));
    }
}
#endif

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2264 KB Output is correct
2 Correct 9 ms 1956 KB Output is correct
3 Correct 9 ms 1956 KB Output is correct
4 Correct 8 ms 2044 KB Output is correct
5 Correct 8 ms 1964 KB Output is correct
6 Correct 8 ms 1956 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2264 KB Output is correct
2 Correct 9 ms 1956 KB Output is correct
3 Correct 9 ms 1956 KB Output is correct
4 Correct 8 ms 2044 KB Output is correct
5 Correct 8 ms 1964 KB Output is correct
6 Correct 8 ms 1956 KB Output is correct
7 Correct 11 ms 2184 KB Output is correct
8 Correct 22 ms 2288 KB Output is correct
9 Correct 23 ms 2292 KB Output is correct
10 Correct 19 ms 2248 KB Output is correct
11 Correct 20 ms 2268 KB Output is correct
12 Correct 23 ms 1876 KB Output is correct
13 Correct 20 ms 2120 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2264 KB Output is correct
2 Correct 9 ms 1956 KB Output is correct
3 Correct 9 ms 1956 KB Output is correct
4 Correct 8 ms 2044 KB Output is correct
5 Correct 8 ms 1964 KB Output is correct
6 Correct 8 ms 1956 KB Output is correct
7 Correct 11 ms 2184 KB Output is correct
8 Correct 22 ms 2288 KB Output is correct
9 Correct 23 ms 2292 KB Output is correct
10 Correct 19 ms 2248 KB Output is correct
11 Correct 20 ms 2268 KB Output is correct
12 Correct 23 ms 1876 KB Output is correct
13 Correct 20 ms 2120 KB Output is correct
14 Incorrect 6 ms 328 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2264 KB Output is correct
2 Correct 9 ms 1956 KB Output is correct
3 Correct 9 ms 1956 KB Output is correct
4 Correct 8 ms 2044 KB Output is correct
5 Correct 8 ms 1964 KB Output is correct
6 Correct 8 ms 1956 KB Output is correct
7 Correct 11 ms 2184 KB Output is correct
8 Correct 22 ms 2288 KB Output is correct
9 Correct 23 ms 2292 KB Output is correct
10 Correct 19 ms 2248 KB Output is correct
11 Correct 20 ms 2268 KB Output is correct
12 Correct 23 ms 1876 KB Output is correct
13 Correct 20 ms 2120 KB Output is correct
14 Incorrect 6 ms 328 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2264 KB Output is correct
2 Correct 9 ms 1956 KB Output is correct
3 Correct 9 ms 1956 KB Output is correct
4 Correct 8 ms 2044 KB Output is correct
5 Correct 8 ms 1964 KB Output is correct
6 Correct 8 ms 1956 KB Output is correct
7 Correct 11 ms 2184 KB Output is correct
8 Correct 22 ms 2288 KB Output is correct
9 Correct 23 ms 2292 KB Output is correct
10 Correct 19 ms 2248 KB Output is correct
11 Correct 20 ms 2268 KB Output is correct
12 Correct 23 ms 1876 KB Output is correct
13 Correct 20 ms 2120 KB Output is correct
14 Incorrect 6 ms 328 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2264 KB Output is correct
2 Correct 9 ms 1956 KB Output is correct
3 Correct 9 ms 1956 KB Output is correct
4 Correct 8 ms 2044 KB Output is correct
5 Correct 8 ms 1964 KB Output is correct
6 Correct 8 ms 1956 KB Output is correct
7 Correct 11 ms 2184 KB Output is correct
8 Correct 22 ms 2288 KB Output is correct
9 Correct 23 ms 2292 KB Output is correct
10 Correct 19 ms 2248 KB Output is correct
11 Correct 20 ms 2268 KB Output is correct
12 Correct 23 ms 1876 KB Output is correct
13 Correct 20 ms 2120 KB Output is correct
14 Incorrect 6 ms 328 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2264 KB Output is correct
2 Correct 9 ms 1956 KB Output is correct
3 Correct 9 ms 1956 KB Output is correct
4 Correct 8 ms 2044 KB Output is correct
5 Correct 8 ms 1964 KB Output is correct
6 Correct 8 ms 1956 KB Output is correct
7 Correct 11 ms 2184 KB Output is correct
8 Correct 22 ms 2288 KB Output is correct
9 Correct 23 ms 2292 KB Output is correct
10 Correct 19 ms 2248 KB Output is correct
11 Correct 20 ms 2268 KB Output is correct
12 Correct 23 ms 1876 KB Output is correct
13 Correct 20 ms 2120 KB Output is correct
14 Incorrect 6 ms 328 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2264 KB Output is correct
2 Correct 9 ms 1956 KB Output is correct
3 Correct 9 ms 1956 KB Output is correct
4 Correct 8 ms 2044 KB Output is correct
5 Correct 8 ms 1964 KB Output is correct
6 Correct 8 ms 1956 KB Output is correct
7 Correct 11 ms 2184 KB Output is correct
8 Correct 22 ms 2288 KB Output is correct
9 Correct 23 ms 2292 KB Output is correct
10 Correct 19 ms 2248 KB Output is correct
11 Correct 20 ms 2268 KB Output is correct
12 Correct 23 ms 1876 KB Output is correct
13 Correct 20 ms 2120 KB Output is correct
14 Incorrect 6 ms 328 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2264 KB Output is correct
2 Correct 9 ms 1956 KB Output is correct
3 Correct 9 ms 1956 KB Output is correct
4 Correct 8 ms 2044 KB Output is correct
5 Correct 8 ms 1964 KB Output is correct
6 Correct 8 ms 1956 KB Output is correct
7 Correct 11 ms 2184 KB Output is correct
8 Correct 22 ms 2288 KB Output is correct
9 Correct 23 ms 2292 KB Output is correct
10 Correct 19 ms 2248 KB Output is correct
11 Correct 20 ms 2268 KB Output is correct
12 Correct 23 ms 1876 KB Output is correct
13 Correct 20 ms 2120 KB Output is correct
14 Incorrect 6 ms 328 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2264 KB Output is correct
2 Correct 9 ms 1956 KB Output is correct
3 Correct 9 ms 1956 KB Output is correct
4 Correct 8 ms 2044 KB Output is correct
5 Correct 8 ms 1964 KB Output is correct
6 Correct 8 ms 1956 KB Output is correct
7 Correct 11 ms 2184 KB Output is correct
8 Correct 22 ms 2288 KB Output is correct
9 Correct 23 ms 2292 KB Output is correct
10 Correct 19 ms 2248 KB Output is correct
11 Correct 20 ms 2268 KB Output is correct
12 Correct 23 ms 1876 KB Output is correct
13 Correct 20 ms 2120 KB Output is correct
14 Incorrect 6 ms 328 KB Incorrect
15 Halted 0 ms 0 KB -