Submission #709866

#	Time	Username	Problem	Language	Result	Execution time	Memory
709866		doowey	화성 (APIO22_mars)	C++17	54 / 100	482 ms	3844 KiB

mars

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

pair<pii, pii> rect(int i, int j, int k, int n){
    int side = 2 * n + 1 - k * 2;
    int len = (2 * n + 1) / side;
    int rem = (2 * n + 1) % side;
    int i0 = i * len;
    int i1 = len;
    if(i >= side - rem){
        i0 += i - (side - rem);
        i1 = len + 1;
    }
    i1 += i0 - 1;
    int j0 = j * len;
    int j1 = len;
    if(j >= side - rem){
        j0 += j - (side - rem);
        j1 = len + 1;
    }
    j1 += j0 - 1;
    return mp(mp(i0, j0), mp(i1, j1));
    //
    // len, len, len, len ... len
}

string process(vector <vector<string>> a, int i, int j, int k, int n)
{
    pair<pii, pii> need = rect(i, j, k + 1, n);
    pair<pii, pii> has;
    int nn = need.se.fi - need.fi.fi + 1;
    int mm = need.se.se - need.fi.se + 1;
    vector<vector<char>> C(nn);
    for(int i = 0 ; i < nn; i ++ ){
        C[i].resize(mm, '0');
    }
    int idx;
    for(int di = 0 ; di < 3; di ++ ){
        for(int dj = 0 ; dj < 3; dj ++ ){
            has = rect(i + di, j + dj, k, n);
            idx = 0;
            for(int p = has.fi.fi; p <= has.se.fi; p ++ ){
                for(int q = has.fi.se; q <= has.se.se; q ++ ){
                    if(need.fi.fi <= p && p <= need.se.fi && need.fi.se <= q && q <= need.se.se){
                        C[p - need.fi.fi][q - need.fi.se] = a[di][dj][idx];
                    }
                    idx ++ ;
                }
            }
        }
    }
    /*
    if(k == 0){
        cout << i << " " << j << "\n";
        for(auto x : C){
            for(auto y : x) cout << y;
            cout << "\n";
        }
        cout << "---------\n";
    }
    */
    if(k < n - 1){
        string ret;
        for(auto ii : C){
            for(auto jj : ii){
                ret.push_back(jj);
            }
        }
        while(ret.size() < 100) ret.push_back('0');
        return ret;
    }
    int cummies = 0;
    queue<pii> G;
    pii nd;
    pii nx;
    int res = 0;
    for(int i = 0 ; i < nn; i ++ ){
        for(int j = 0 ; j < mm ; j ++ ){
            if(C[i][j] == '1'){
                G.push(mp(i,j));
                C[i][j]='0';
                res ++ ;
                while(!G.empty()){
                    nd = G.front();
                    G.pop();
                    for(int di = -1; di <= +1; di ++ ){
                        for(int dj = -1; dj <= + 1; dj ++ ){
                            if(abs(di) + abs(dj) == 1){
                                nx = mp(nd.fi + di, nd.se + dj);
                                if(nx.fi >= 0 && nx.se >= 0 && nx.fi < nn && nx.se < mm){
                                    if(C[nx.fi][nx.se] == '1'){
                                        C[nx.fi][nx.se] = '0';
                                        G.push(nx);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    string soln;
    for(int i = 0 ; i < 25; i ++ ){
        if((res & (1 << i))) soln.push_back('1');
        else soln.push_back('0');
    }
    while(soln.size() < 100) soln.push_back('0');
    return soln;
}

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:81:9: warning: unused variable 'cummies' [-Wunused-variable]
   81 |     int cummies = 0;
      |         ^~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 7 / 7
• Subtask 6: 8 / 8
• Subtask 7: 10 / 10
• Subtask 8: 0 / 24
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11