Submission #973642

#	Time	Username	Problem	Language	Result	Execution time	Memory
973642		Pannda	Mars (APIO22_mars)	C++17	0 / 100	1 ms	332 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) {
        int d = 2 * n + 1 - m;
        vector<vector<bool>> mp = [&] {
            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';
                }
            }
            for (int y = 0; y < 2; y++) {
                for (int x = 2; x < d; x++) {
                    mp[x][y] = a[2][y][x - 2] - '0';
                }
            }
            for (int x = 2; x < d; x++) {
                for (int y = 2; y < d; y++) {
                    if (x == 2) {
                        mp[x][y] = a[2][2][y - 2] - '0';
                    } else if (y == 2) {
                        mp[x][y] = a[2][2][d - 2 + x - 1] - '0';
                    } else {
                        mp[x][y] = 0;
                    }
                }
            }
            return mp;
        }();
        int fetch = string_to_int(a[2][2].substr(81));
        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;
        };
        int siz = 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] = siz++;
                }
            }
        }
        DSU dsu(siz + 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]);
                    }
                }
            }
        }
        if (k == n - 1) {
            return int_to_string(dsu.count() - 1 + fetch, 100);
        } else {
            string res;
            for (int y = 0; y < d; y++) {
                res.push_back('0' + mp[0][y]);
                if (mp[0][y]) dsu.unionize(id[0][y], siz);
            }
            for (int x = 1; x < d; x++) {
                res.push_back('0' + mp[x][0]);
                if (mp[x][0]) dsu.unionize(id[x][0], siz);
            }
            while (res.size() < 81) res.push_back('0');
            res += int_to_string(dsu.count() - 1 + fetch, 19);
            return res;
        }
    } else if (i < j) {
        string s(100, '0');
        s[0] = a[0][0][0];
        s[1] = a[0][1][0];
        for (int x = 2; x < 100; x++) {
            s[x] = a[0][2][x - 2];
        }
        return s;
    } else {
        string s(100, '0');
        s[0] = a[0][0][0];
        s[1] = a[1][0][0];
        for (int x = 2; x < 100; x++) {
            s[x] = a[2][0][x - 2];
        }
        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++) {
      |                     ~~^~~~~~~~~~

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