Submission #982792

#	Time	Username	Problem	Language	Result	Execution time	Memory
982792		vjudge1	Mars (APIO22_mars)	C++17	29 / 100	98 ms	4588 KiB

mars

#include "mars.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;

string process (vector <vector <string> > a, int i, int j, int k, int n) {
    n = 2*n+1;
    if (n == 3) {
        vector <vector <char> > mat(n, vector <char> (n, false));
        for (ll ii = 0; ii < 3; ii++) {
            for (ll jj = 0; jj < 3; jj++) {
                mat[ii][jj] = a[ii][jj][0];
            }
        }
        vector <vector <char> > vis(n, vector <char> (n, false));
        ll ans = 0;
        for (ll i = 0; i < n; i++) {
            for (ll j = 0; j < n; j++) {
                if (mat[i][j] == '0') continue;
                if (vis[i][j]) continue;
                ans++;
                queue <ll> q;
                q.push(i);
                q.push(j);
                while (q.size()) {
                    ll i = q.front(); q.pop();
                    ll j = q.front(); q.pop();
                    if (mat[i][j] == '0') continue;
                    if (vis[i][j]) continue;
                    vis[i][j] = true;
                    if (0 < i) {
                        q.push(i-1);
                        q.push(j);
                    }
                    if (i < n-1) {
                        q.push(i+1);
                        q.push(j);
                    }
                    if (0 < j) {
                        q.push(i);
                        q.push(j-1);
                    }
                    if (j < n-1) {
                        q.push(i);
                        q.push(j+1);
                    }
                }
            }
        }
        string sans(100, '0');
        for (ll i = 0; i < 10; i++) {
            sans[i] = (ans>>i&1 ? '1' : '0');
        }
        return sans;
    }
    vector <vector <bitset <100> > > aa(3, vector <bitset <100> > (3, bitset <100> (0)));
    if (k == 0) {
        for (ll ii = i; ii < i+3; ii++) {
            for (ll jj = j; jj < j+3; jj++) {
                swap(a[ii-i][jj-j][0], a[ii-i][jj-j][(ii/2)*((n+1)/2)+(jj/2)]);
            }
        }
    }
    for (ll i = 0; i < 3; i++) {
        for (ll j = 0; j < 3; j++) {
            for (ll k = 0; k < 100; k++) {
                aa[i][j][k] = a[i][j][k] == '1';
            }
        }
    }
    aa[0][0] |= aa[0][2];
    aa[0][0] |= aa[2][0];
    aa[0][0] |= aa[2][2];
    aa[0][1] |= aa[2][1];
    aa[1][0] |= aa[1][2];
    if (k+1 != n/2) {
        string ans = "";
        for (ll k = 0; k < 100; k++) ans += char('0'+aa[0][0][k]);
        return ans;
    }
    // final phase
    vector <vector <char> > mat(n, vector <char> (n, '*'));
    for (ll sti = 0; sti < 2; sti++) {
    for (ll stj = 0; stj < 2; stj++) {
        for (ll i = sti; i < n; i += 2) {
            for (ll j = stj; j < n; j += 2) {
                ll pos = (i/2)*((n+1)/2)+(j/2);
                mat[i][j] = '0'+aa[sti][stj][pos];
            }
        }
    }}
    vector <vector <char> > vis(n, vector <char> (n, false));
    ll ans = 0;
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            if (mat[i][j] == '0') continue;
            if (vis[i][j]) continue;
            ans++;
            queue <ll> q;
            q.push(i);
            q.push(j);
            while (q.size()) {
                ll i = q.front(); q.pop();
                ll j = q.front(); q.pop();
                if (mat[i][j] == '0') continue;
                if (vis[i][j]) continue;
                vis[i][j] = true;
                if (0 < i) {
                    q.push(i-1);
                    q.push(j);
                }
                if (i < n-1) {
                    q.push(i+1);
                    q.push(j);
                }
                if (0 < j) {
                    q.push(i);
                    q.push(j-1);
                }
                if (j < n-1) {
                    q.push(i);
                    q.push(j+1);
                }
            }
        }
    }
    string sans(100, '0');
    for (ll i = 0; i < 10; i++) {
        sans[i] = (ans>>i&1 ? '1' : '0');
    }
    return sans;
}

• 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