Submission #572816

#	Time	Username	Problem	Language	Result	Execution time	Memory
572816		baluteshih	Mars (APIO22_mars)	C++17	21 / 100	51 ms	2784 KiB

mars

#include "mars.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(), v.end()
#define pb push_back

char mp[100][100];
pii boss[100][100];
pii mapping[100000];

pii finds(pii a) {
    if (a == pii(-1, -1)) return pii(-1, -1);
    if (a == boss[a.X][a.Y]) return a;
    return boss[a.X][a.Y] = finds(boss[a.X][a.Y]);
}

int Union(pii a, pii b) {
    a = finds(a), b = finds(b);
    if (a == b)
        return 0;
    if (a > b)
        swap(a, b);
    //cerr << "Union " << a.X << " " << a.Y << " " << b.X << " " << b.Y << "\n";
    boss[b.X][b.Y] = a;
    return 1;
}

string process(vector<vector<string>> a, int i, int j, int k, int n) {
    const int ANS = __lg(((2 * n + 1) * (2 * n + 1) + 1) / 2) + 1;
    const int SZ = 4; 

    auto decode = [&](string s) {
        int rt = 0;
        for (int t = 0; t < SZ(s); ++t)
            if (s[t] == '1')
                rt |= 1 << t;
        return rt;
    };

    auto encode = [](int x, int len) {
        string rt(len, '0');
        for (int t = 0; t < len; ++t)
            if (x >> t & 1)
                rt[t] = '1', x -= 1 << t;
        assert(x == 0);
        return rt;
    };

    int m = 2 * (n - k - 1);
    int num = 2 * n - (m + 2) + 2 * n - (m + 2);
    int nxt = 2 * n - (m) + 2 * n - (m);

    auto place = [&](int p, int q, int tm) {
        if (q == tm + 2)
            return 2 * n - p;
        return 2 * n - (tm + 3) + p - (tm + 2);
    };

    auto coord = [&](int x, int tm) {
        if (x <= 2 * n - (tm + 3))
            return pii(2 * n - x, tm + 2);
        x -= 2 * n - (tm + 3);
        return pii(tm + 2, x + tm + 2);
    };

    auto check = [&](int x, int y) {
        if (x < m || x >= 2 * n + 1) return 0;
        if (y < m || y >= 2 * n + 1) return 0;
        if (x > m + 2 && y > m + 2) return 0;
        if (boss[x][y].X == -1) return 0;
        return 1;
    };

    if (i == m && j == m) {

        if (k == 0 && a[2][2][0] == '1') {
            a[2][2][100 - ANS] = '1';
            a[2][2][1] = '1';
        }

        int sum = decode(a[2][2].substr(100 - ANS, ANS));
        //cerr << "prv sum = " << sum << "\n";
        for (int p = m; p < m + 3; ++p)
            for (int q = m; q < m + 3; ++q) {
                mp[p][q] = a[p - m][q - m][0];
                boss[p][q] = pii(p, q);
                if (mp[p][q] == '1')
                    sum += (p != m + 2 || q != m + 2);
                else
                    boss[p][q] = pii(-1, -1);
            }
        for (int p = m; p < m + 2; ++p)
            for (int q = m + 3; q < 2 * n + 1; ++q) {
                mp[p][q] = a[p - m][2][q - m - 2];
                mp[q][p] = a[2][p - m][q - m - 2];
                boss[p][q] = pii(p, q);
                if (mp[p][q] == '1')
                    ++sum;
                else
                    boss[p][q] = pii(-1, -1);
                boss[q][p] = pii(q, p);
                if (mp[q][p] == '1')
                    ++sum;
                else
                    boss[q][p] = pii(-1, -1);
            }
        //cerr << "sum = " << sum << "\n";
        for (int p = 0; p < num; ++p)
            mapping[p] = pii(2 * n + 1, 2 * n + 1);
        mapping[0] = pii(-1, -1);
        for (int p = 0, nw = 1; p < num; ++p, nw += SZ) {
            int d = decode(a[2][2].substr(nw, SZ));
            pii c = coord(p, m);
            mapping[d] = min(mapping[d], c);
        }
        for (int p = 0, nw = 1; p < num; ++p, nw += SZ) {
            int d = decode(a[2][2].substr(nw, SZ));
            pii c = coord(p, m);
            //cerr << c.X << " " << c.Y << " code = " << d << ", mapping = " << mapping[d].X << " " << mapping[d].Y << "\n";
            boss[c.X][c.Y] = mapping[d];
        }
        /*for (int p = m; p < 2 * n + 1; ++p)
            for (int q = m; q < 2 * n + 1; ++q)
                if (check(p, q)) {
                    cerr << "boss " << p << " " << q << " = " << boss[p][q].X << " " << boss[p][q].Y << "\n";
                }*/
        if (check(m + 2, m + 2)) {
            if (check(m + 3, m + 2))
                Union(pii(m + 2, m + 2), pii(m + 3, m + 2));
            if (check(m + 2, m + 3))
                Union(pii(m + 2, m + 2), pii(m + 2, m + 3));
        }
        for (int p = m; p < 2 * n + 1; ++p)
            for (int q = m; q < 2 * n + 1; ++q)
                if (check(p, q)) {
                    if (check(p + 1, q))
                        sum -= Union(pii(p, q), pii(p + 1, q));
                    if (check(p, q + 1))
                        sum -= Union(pii(p, q), pii(p, q + 1));
                }
        if (k == n - 1)
            return encode(sum, ANS) + string(100 - ANS, '0');
        string rt(1, a[0][0][0]);

        vector<pii> ele(1, pii(-1, -1));
        for (int p = 0; p < nxt; ++p) {
            pii c = coord(p, m - 2);
            ele.pb(finds(c));
        }
        sort(ALL(ele)), ele.resize(unique(ALL(ele)) - ele.begin());
        for (int p = 0; p < nxt; ++p) {
            pii c = coord(p, m - 2);
            rt += encode(lower_bound(ALL(ele), finds(c)) - ele.begin(), SZ);
        }

        rt.resize(100 - ANS, '0');
        return rt + encode(sum, ANS);
    }
    if (i == m) {
        a[2][0].pop_back(), a[2][0].pop_back();
        a[2][0].insert(a[2][0].begin(), a[1][0][0]);
        a[2][0].insert(a[2][0].begin(), a[0][0][0]);
        return a[2][0];
    }
    if (j == m) {
        a[0][2].pop_back(), a[0][2].pop_back();
        a[0][2].insert(a[0][2].begin(), a[0][1][0]);
        a[0][2].insert(a[0][2].begin(), a[0][0][0]);
        return a[0][2];
    }
    return a[0][0];
}

Compilation message (stderr)

mars.cpp: In function 'std::string process(std::vector<std::vector<std::__cxx11::basic_string<char> > >, int, int, int, int)':
mars.cpp:59:10: warning: variable 'place' set but not used [-Wunused-but-set-variable]
   59 |     auto place = [&](int p, int q, int tm) {
      |          ^~~~~

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 7 / 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