Submission #578181

#	Time	Username	Problem	Language	Result	Execution time	Memory
578181		johnf	Mars (APIO22_mars)	C++17	14 / 100	17 ms	2312 KiB

mars

#include "mars.h"
#include <bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define for0(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

using ll = long long;
using ld = long double;
using vi = vector<int>;

template <class T>
bool uin(T &a, T b) {
    return a > b ? (a = b, true) : false;
}
template <class T>
bool uax(T &a, T b) {
    return a < b ? (a = b, true) : false;
}

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

namespace subn4 {
std::string process(std::vector<std::vector<std::string>> &a, int &row, int &col, int &phase, int &n) {
    int N = n * 2 + 1;
    string ans(100, '0');
    if (phase == 0) {
        // first phase
        fore(i, row, row + 2) {
            fore(j, col, col + 2) {
                if (a[i - row][j - col][0] == '1') {
                    ans[i * N + j] = '1';
                }
            }
        }
    } else {
        fore(i, row, row + 2) {
            fore(j, col, col + 2) {
                for0(k, 100) {
                    if (a[i - row][j - col][k] == '1') {
                        ans[k] = '1';
                    }
                }
            }
        }
    }
    debug(row, col, phase, ans);
    if (phase == n - 1) {
        // then lol
        const pair<int, int> d[] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
        vector<vector<int>> flag(N, vector<int>(N));
        int cnt = 0;
        for0(i, N) {
            for0(j, N) {
                if (!flag[i][j] && ans[i * N + j] == '1') {
                    cnt++;
                    queue<pair<int, int>> q;
                    q.emplace(i, j);
                    flag[i][j] = 1;
                    while (!q.empty()) {
                        int x, y;
                        tie(x, y) = q.front();
                        q.pop();
                        for (auto [dx, dy] : d) {
                            int nx = x + dx, ny = y + dy;
                            if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
                                if (!flag[nx][ny] && ans[nx * N + ny] == '1') {
                                    flag[nx][ny] = 1;
                                    q.emplace(nx, ny);
                                }
                            }
                        }
                    }
                }
            }
        }
        ans = string(100, '0');
        for0(i, 31) { ans[i] = '0' + (cnt >> i & 1); }
    }
    return ans;
}
}

std::string process(std::vector<std::vector<std::string>> a, int i, int j, int k, int n) {
    if (n <= 4) {
        return subn4::process(a, i, j, k, n);
    }
}

Compilation message (stderr)

mars.cpp: In function 'std::string subn4::process(std::vector<std::vector<std::__cxx11::basic_string<char> > >&, int&, int&, int&, int&)':
mars.cpp:20:20: warning: statement has no effect [-Wunused-value]
   20 | #define debug(...) 42
      |                    ^~
mars.cpp:62:5: note: in expansion of macro 'debug'
   62 |     debug(row, col, phase, ans);
      |     ^~~~~
mars.cpp: In function 'std::string process(std::vector<std::vector<std::__cxx11::basic_string<char> > >, int, int, int, int)':
mars.cpp:103:1: warning: control reaches end of non-void function [-Wreturn-type]
  103 | }
      | ^

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