Submission #973766

#	Time	Username	Problem	Language	Result	Execution time	Memory
973766		Pannda	Mars (APIO22_mars)	C++17	100 / 100	772 ms	6820 KiB

mars

#include "mars.h"

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    int cnt;
    vector<int> f;

    DSU(int n) : cnt(n), f(n) { iota(f.begin(), f.end(), 0); }

    int leader(int u) {
        while (u != f[u]) {
            u = f[u] = f[f[u]];
        }
        return u;
    }

    bool unionize(int u, int v) {
        u = leader(u);
        v = leader(v);
        if (u == v) return false;
        f[u] = v;
        cnt--;
        return true;
    }

    int count() {
        return cnt;
    }

    bool same(int u, int v) {
        return leader(u) == leader(v);
    }
};

int string_to_int(string s) {
    int res = 0;
    for (int i = 0; i < s.size(); i++) {
        res += (s[i] - '0') * (1 << i);
    }
    return res;
}

string int_to_string(int x, int length) {
    string res;
    for (int i = 0; i < length; i++) {
        res.push_back('0' + (x & 1));
        x >>= 1;
    }
    return res;
}

string _process(vector<vector<string>> a, int i, int j, int k, int n)
{
    int m = 2 * (n - k - 1);
    if (i != m && j != m) return a[0][0];

    if (i < j) {
        string s(100, '0');
        s[0] = a[0][0][0];
        s[1] = a[0][1][0];
        for (int x = 2; x < 50; x++) {
            s[x] = a[0][2][x - 2];
        }
        s[50] = a[1][0][0];
        s[51] = a[1][1][0];
        for (int x = 52; x < 100; x++) {
            s[x] = a[1][2][x - 52];
        }
        return s;
    }

    if (i > j) {
        string s(100, '0');
        s[0] = a[0][0][0];
        s[1] = a[1][0][0];
        for (int x = 2; x < 50; x++) {
            s[x] = a[2][0][x - 2];
        }
        s[50] = a[0][1][0];
        s[51] = a[1][1][0];
        for (int x = 52; x < 100; x++) {
            s[x] = a[2][1][x - 52];
        }
        return s;
    }

    int d = 2 * n + 1 - m;

    vector<array<int, 2>> dxy = { {-1, 0}, {+1, 0}, {0, -1}, {0, +1} };
    auto valid = [&](int x, int y) {
        if (x < 0 || x >= d || y < 0 || y >= d) return false;
        return true;
    };
    auto neighbour = [&](int x, int y) {
        vector<array<int, 2>> res;
        for (auto [dx, dy] : dxy) {
            if (valid(x + dx, y + dy)) res.push_back({x + dx, y + dy});
        }
        return res;
    };

    auto [mp, cnt, id] = [&]() -> tuple<vector<vector<bool>>, int, vector<vector<int>>> {
        vector<vector<bool>> mp(d, vector<bool>(d, 0));
        for (int x = 0; x < 2; x++) {
            for (int y = 0; y < 2; y++) {
                mp[x][y] = a[x][y][0] - '0';
            }
        }
        for (int x = 0; x < 2; x++) {
            for (int y = 2; y < d; y++) {
                mp[x][y] = a[x][2][y - 2] - '0';
                mp[x + 1][y] = k == 0 ? a[x + 1][2][y - 2] - '0' : a[x][2][50 + y - 2] - '0';
            }
        }
        for (int y = 0; y < 2; y++) {
            for (int x = 2; x < d; x++) {
                mp[x][y] = a[2][y][x - 2] - '0';
                mp[x][y + 1] = k == 0 ? a[2][y + 1][x - 2] - '0' : a[2][y][50 + x - 2] - '0';
            }
        }
        int cnt = 0;
        vector<vector<int>> id(d, vector<int>(d, -1));
        for (int x = 0; x < d; x++) {
            for (int y = 0; y < d; y++) {
                if (mp[x][y]) {
                    id[x][y] = cnt++;
                }
            }
        }
        return {mp, cnt, id};
    }();

    DSU dsu(cnt + 1);
    for (int x = 0; x < d; x++) {
        for (int y = 0; y < d; y++) {
            for (auto [xx, yy] : neighbour(x, y)) {
                if (mp[x][y] && mp[xx][yy]) {
                    dsu.unionize(id[x][y], id[xx][yy]);
                }
            }
        }
    }

    auto [config, seq] = [&] {
        vector<array<int, 2>> config;
        vector<int> seq;
        for (int x = d - 1; x >= 2; x--) if (mp[x][2] && (x == d - 1 || !mp[x + 1][2])) config.push_back({x, 2});
        for (int y = 3; y < d; y++) if (mp[2][y] && !mp[2][y - 1]) config.push_back({2, y});
        for (int i = 0; i < config.size(); i++) seq.push_back(string_to_int(a[2][2].substr(2 * i, 2)));
        if (k == 0 && !seq.empty()) seq[0] = 0;
        return make_pair(config, seq);
    }();

    vector<array<int, 2>> stk;
    for (int i = 0; i < config.size(); i++) {
        if (seq[i] & 1) { // close
            auto [x, y] = config[i];
            auto [xx, yy] = stk.back();
            dsu.unionize(id[x][y], id[xx][yy]);
            stk.pop_back();
        }
        if (seq[i] & 2) { // open
            stk.push_back(config[i]);
        }
    }

    int fetch = string_to_int(a[2][2].substr(85));

    if (k == n - 1) {
        return int_to_string(dsu.count() - 1 + fetch, 100);
    } else {
        string res;
        vector<array<int, 2>> config;
        for (int x = d - 1; x >= 0; x--) if (mp[x][0] && (x == d - 1 || !mp[x + 1][0])) config.push_back({x, 0});
        for (int y = 1; y < d; y++) if (mp[0][y] && !mp[0][y - 1]) config.push_back({0, y});
        for (int i = 0; i < config.size(); i++) {
            bool close = false;
            bool open = false;
            auto [x, y] = config[i];
            for (int j = 0; j < config.size(); j++) {
                auto [xx, yy] = config[j];
                if (dsu.same(id[x][y], id[xx][yy])) {
                    if (j < i) close = true;
                    if (i < j) open = true;
                }
            }
            res.push_back('0' + close);
            res.push_back('0' + open);
        }
        for (auto [x, y] : config) {
            dsu.unionize(id[x][y], cnt);
        }
        while (res.size() < 85) res.push_back('0');
        res += int_to_string(dsu.count() - 1 + fetch, 15);
        return res;
    }
}

string process(vector<vector<string>> a, int i, int j, int k, int n) {
    string s = _process(a, i, j, k, n);
//    cout << k << ' ' << i << ' ' << j << ": " << s << '\n';
    return s;
}

Compilation message (stderr)

mars.cpp: In function 'int string_to_int(std::string)':
mars.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i = 0; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~
mars.cpp: In lambda function:
mars.cpp:151:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |         for (int i = 0; i < config.size(); i++) seq.push_back(string_to_int(a[2][2].substr(2 * i, 2)));
      |                         ~~^~~~~~~~~~~~~~~
mars.cpp: In function 'std::string _process(std::vector<std::vector<std::__cxx11::basic_string<char> > >, int, int, int, int)':
mars.cpp:157:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |     for (int i = 0; i < config.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
mars.cpp:178:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |         for (int i = 0; i < config.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~
mars.cpp:182:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  182 |             for (int j = 0; j < config.size(); j++) {
      |                             ~~^~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 7 / 7
• Subtask 6: 8 / 8
• Subtask 7: 10 / 10
• Subtask 8: 24 / 24
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11