Submission #1167042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167042		SmuggingSpun	Mars (APIO22_mars)	C++20	29 / 100	73 ms	3820 KiB

mars

#include "mars.h"
#include<bits/stdc++.h>
using namespace std;
string to_binary(int number){
    string ret = "";
    for(int i = 0; i < 30; i++){
        ret += char((number >> i & 1) + 48);
    }
    return ret + string(70, '0');
}
int count_scc(vector<vector<bool>>a){
    function<void(int, int)>dfs;
    dfs = [&] (int i, int j){
        if(i < 0 || i >= a.size() || j < 0 || j >= a.size() || !a[i][j]){
            return;
        }
        a[i][j] = false;
        dfs(i, j - 1);
        dfs(i, j + 1);
        dfs(i - 1, j);
        dfs(i + 1, j);
    };
    int ans = 0;
    for(int i = 0; i < a.size(); i++){
        for(int j = 0; j < a.size(); j++){
            if(a[i][j]){
                dfs(i, j);
                ans++;
            }
        }
    }
    return ans;
}
string process(vector<vector<string>>a, int i, int j, int k, int n){
    if(n == 1){
        int ans = 0;
        vector<vector<bool>>vis(4, vector<bool>(4, false));
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                if(a[i][j][0] == '1'){
                    vis[i][j] = true;
                }
            }
        }
        return to_binary(count_scc(vis));
    }
    if(n == 2){
        if(k == 0){
            string ans(100, '0');
            for(int i = 0; i < 3; i++){
                for(int j = 0; j < 3; j++){
                    if(a[i][j][0] == '1'){
                        ans[i * 3 + j] = '1';
                    }
                }
            }
            return ans;
        }
        vector<vector<bool>>board(5, vector<bool>(5, false));
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                for(int x = 0; x < 3; x++){
                    for(int y = 0; y < 3; y++){
                        if(a[i][j][x * 3 + y] == '1'){
                            board[i + x][j + y] = true;
                        }
                    }
                }                
            }
        }
        return to_binary(count_scc(board));
    }
    if(n <= 5){
        int N = (k << 1) + 1;
        vector<vector<bool>>board(N + 2, vector<bool>(N + 2, false));
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                for(int t = 0; t < N * N; t++){
                    if(a[i][j][t] == '1'){
                        board[i + t / N][j + t % N] = true;
                    }
                }
            }
        }
        if(k == n - 1){
            return to_binary(count_scc(board));
        }
        string ans(100, '0');
        for(int i = 0; i < N + 2; i++){
            for(int j = 0; j < N + 2; j++){
                if(board[i][j]){
                    ans[i * (N + 2) + j] = '1';
                }
            }
        }
        return ans;
    }
    if(n <= 10){
        int N = (k << 1) + 1;
        if(N < 8){
            vector<vector<bool>>board(N + 2, vector<bool>(N + 2, false));
            for(int i = 0; i < 3; i++){
                for(int j = 0; j < 3; j++){
                    for(int t = 0; t < N * N; t++){
                        if(a[i][j][t] == '1'){
                            board[i + t / N][j + t % N] = true;
                        }
                    }
                }
            }
            string ans(100, '0');
            for(int i = 0; i < N + 2; i++){
                for(int j = 0; j < N + 2; j++){
                    if(board[i][j]){
                        ans[i * (N + 2) + j] = '1';
                    }
                }
            }
            return ans;
        }
        int p = (n << 1) - N + 1;
        if(k < n - 1){
            if(i + 2 == p && j == 0){
                return a[2][0];
            }
            if(i == 0 && j + 2 == p){
                return a[0][2];
            }
            if(i + 2 == p && j + 2 == p){
                return a[2][2];
            }
            return a[0][0];
        }
        vector<vector<bool>>board((n << 1) + 1, vector<bool>((n << 1) + 1, false));
        for(int i = 0; i < 100; i++){
            if(a[0][0][i] == '1'){
                board[i / 9][i % 9] = true;
            }
            if(a[p][0][i] == '1'){
                board[i / 9 + (n << 1) - 8][i % 9] = true;
            }
            if(a[0][p][i] == '1'){
                board[i / 9][i % 9 + (n << 1) - 8] = true;
            }
            if(a[p][p][i] == '1'){
                board[i / 9 + (n << 1) - 8][i % 9 + (n << 1) - 8] = true;
            }
        }
        return to_binary(count_scc(board));
    }
}

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

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