Submission #1225235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225235		SpyrosAliv	Mars (APIO22_mars)	C++20	14 / 100	10 ms	3480 KiB

mars

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

vector<pair<int, int>> delta = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
vector<vector<bool>> vis;
int N;

bool inside(int i, int j) {
    return i >= 0 && i < N && j >= 0 && j < N;
}

void dfs(int i, int j, vector<vector<char>> &grid) {
    if (!inside(i, j) || vis[i][j] || grid[i][j] == '0') return;
    vis[i][j] = true;
    for (auto [pi, pj]: delta) dfs(i + pi, j + pj, grid);
}

int get_comps(vector<vector<char>> grid) {
    N = grid.size();
    vis.assign(N, vector<bool>(N, false));
    int ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (vis[i][j] || grid[i][j] == '0') continue;
            ans++;
            dfs(i, j, grid);
        }
    }
    return ans;
}

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 == m && j != m) {
        // construct column
		//cout << "COLUMN: " << i << " " << j << "\n";
        string fin = "";
        fin += a[0][0][0];
        fin += a[1][0][0];
		//cout << a[2][0] << "\n";
        fin += a[2][0];
        while (fin.size() > 100) fin.pop_back();
		//cout << fin << "\n";
		//cout << "\n";
        return fin;
    }
    else if (j == m && i != m) {
        // construct row;
		//cout << "ROW: " << i << " " << j << "\n";
        string fin = "";
        fin += a[0][0][0];
        fin += a[0][1][0];
        fin += a[0][2];
        while (fin.size() > 100) fin.pop_back();
		//cout << fin << "\n";
        return fin;
    }
    else if (i == m && j == m) { // construct the grid
        int sz = (2*n+1) - i;
        vector<vector<char>> grid(sz, vector<char>(sz, '0'));
        for (int r = 0; r < 2; r++) {
            for (int c = 0; c < 2; c++) {
                grid[r][c] = a[r][c][0];
            }
        }
        for (int r = 2; r < sz; r++) {
            grid[0][r] = a[0][2][r - 2];
            grid[1][r] = a[1][2][r - 2];
        }
        for (int c = 2; c < sz; c++) {
            grid[c][0] = a[2][0][c - 2];
            grid[c][1] = a[2][1][c - 2];
        }
        int sz2 = (2*n+1) - i - 2;
        vector<vector<char>> otherGrid(sz2, vector<char>(sz2));
        for (int r = 0; r < sz2; r++) {
            for (int c = 0; c < sz2; c++) {
                otherGrid[r][c] = a[2][2][sz2 * r + c];
            }
        }
        for (int r = 2; r < sz; r++) {
            for (int c = 2; c < sz; c++) {
                grid[r][c] = otherGrid[r - 2][c - 2];
            }
        }
        if (k == n-1) {
            int x = get_comps(grid);
			//cout << "GRID:\n";
			for (int r = 0; r < sz; r++) {
				for (int c = 0; c < sz; c++) {
					//cout << grid[r][c] << " ";
				}
				//cout << "\n";
			}
            string ans = "";
            for (int b = 0; b < 12; b++) {
                if ((x >> b) & 1) ans += '1';
                else ans += '0';
            }
			while (ans.size() < 100) ans += '0';
            return ans;
        }
        else {
            string ret = "";
            for (int r = 0; r < sz; r++) {
                for (int c = 0; c < sz; c++) {
                    ret += grid[r][c];
                }
            }
            while (ret.size() < 100) ret += '0';
            return ret;
        }
    }
}

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:116:1: warning: control reaches end of non-void function [-Wreturn-type]
  116 | }
      | ^

• 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