Submission #710840

#	Time	Username	Problem	Language	Result	Execution time	Memory
710840		doowey	Mars (APIO22_mars)	C++17	100 / 100	1389 ms	5416 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
}
 
vector<pii> gen_corner(int nn, int mm, int i0, int j0){
    vector<pii> A;
 
    if(i0 != j0){
        for(int i = 0 ; i < nn; i ++ ){
            for(int j = 0 ; j < mm ; j ++ ){
                if(i == (1 - i0/2) * (nn - 1) || j == (1 - j0/2) * (mm - 1)){
                    A.push_back(mp(i, j));
                }
            }
        }
    }
    else{
        for(int i = nn - 1 ; i >= 0; i -- ){
            for(int j = 0 ; j < mm ; j ++ ){
                if(i == (1 - i0/2) * (nn - 1) || j == (1 - j0/2) * (mm - 1)){
                    A.push_back(mp(i, j));
                }
            }
        }
    }
 
    //sort(A.begin(), A.end());
    return A;
}
 
vector<vector<int>> cmp;
 
int calc(vector<vector<char>> C){
    cmp.clear();
 
    int nn = C.size();
    int mm = C[0].size();
    cmp.resize(nn);
    queue<pii> G;
    pii nd;
    pii nx;
    int res = 0;
    int mark = 0;
    for(int i = 0; i < nn; i ++ ) cmp[i].resize(mm);
    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 ++ ;
                mark ++ ;
                while(!G.empty()){
                    nd = G.front();
                    cmp[nd.fi][nd.se] = mark;
                    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);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return res;
}
 
string make_number(int res){
    string sha;
    for(int i = 0 ; i < 25; i ++ ){
        if((res & (1 << i))){
            sha.push_back('1');
        }
        else{
            sha.push_back('0');
        }
    }
    while(sha.size() < 100) sha.push_back('0');
    return sha;
}
 
pair<pii, pii> half(int ii, int jj, int n){
    pii ai = mp((ii/2) * n, (jj/2) * n);
    pii bi = ai;
    bi.fi += n - 1 + ii/2;
    bi.se += n - 1 + jj/2;
    return mp(ai, bi);
}
 
vector<vector<pii>> R;
 
pii fin(pii ai){
    if(R[ai.fi][ai.se] == ai){
        return ai;
    }
    return R[ai.fi][ai.se]=fin(R[ai.fi][ai.se]);
}
 
int total;
bool join(pii ai, pii bi){
    if(R[ai.fi][ai.se].fi == -1 || R[bi.fi][bi.se].fi == -1) return false;
    ai=fin(ai);
    bi=fin(bi);
    if(ai==bi) return false;
    R[ai.fi][ai.se]=bi;
    return true;
}
 
string process(vector <vector<string>> a, int i, int j, int k, int n)
{
    if(n == 1){
        vector<vector<char>> C(3);
        for(int i = 0 ; i < 3; i ++ ){
            C[i].resize(3);
            for(int j = 0 ; j < 3; j ++ ){
                C[i][j] = a[i][j][0];
            }
        }
        return make_number(calc(C));
    }
    pair<pii, pii> need = rect(i, j, k + 1, n);
    if((2 * n + 1) - k * 2 == 5){
        if((i == 0 || i == 2) && (j == 0 || j == 2)){
            pii A = mp((i/2) * n, (j/2) * n);
            pii B = A;
            B.fi += n - 1 + i/2;
            B.se += n - 1 + j/2;
            need = mp(A, B);
        }
    }
    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 < n - 2){
        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 q;
    if(k == n - 2){
        if((i == 0 || i == 2) && (j == 0 || j == 2)){
            vector<pii> lis = gen_corner(nn, mm, i, j);
            int comp = calc(C);
            string res = make_number(comp);
            int id = 10;
            vector<int> ids;
            for(int p = 0 ;p < lis.size(); p ++ ){
                if(C[lis[p].fi][lis[p].se] == '1'){
                    res[id] = '1';
                    if(p && C[lis[p].fi][lis[p].se] == C[lis[p - 1].fi][lis[p - 1].se]){
                        id ++ ;
                        res[id] = '0';
                        ids.pop_back();
                    }
                    else{
                        q = -1;
                        for(int yo = (int)ids.size() - 1; yo >= 0; yo -- ){
                            if(cmp[lis[ids[yo]].fi][lis[ids[yo]].se] == cmp[lis[p].fi][lis[p].se]){
                                q = yo;
                                break;
                            }
                        }
                        if(q == -1){
                            id ++ ;
                            res[id] = '0';
                        }
                        else{
                            while(ids.size() > q){
                                id ++ ;
                                res[id] = '1';
                                ids.pop_back();
                            }
                            id ++ ;
                            res[id] = '0';
                        }
                    }
                    ids.push_back(p);
                    id ++ ;
                }
                else{
                    id ++ ;
                }
            }
            return res;
        }
        else{
            return a[0][0];
        }
    }
    else{
        total = 0;
        for(int ii = 0 ; ii < 10; ii ++ ){
            for(int p = 0; p <= 2; p += 2){
                for(int q = 0; q <= 2; q += 2){
                    total += (a[p][q][ii] - '0') * (1 << ii);
                }
            }
        }
        int trav;
        pair<pii, pii> oo;
        R.clear();
        R.resize(2 * n + 1);
        pii las;
        for(int ii = 0; ii < 2 * n + 1; ii ++ ){
            R[ii].resize(2 * n + 1, mp(-1, -1));
        }
        for(int p = 0; p <= 2; p += 2 ){
            for(int q = 0; q <= 2; q += 2){
                oo = half(p, q, n);
 
                trav = 10;
                vector<pii> B = gen_corner(oo.se.fi - oo.fi.fi + 1, oo.se.se - oo.fi.se + 1, p, q);
                vector<pii> GG;
                pii las;
                for(int it = 0 ; it < B.size() ;it ++ ){
                    B[it].fi += oo.fi.fi;
                    B[it].se += oo.fi.se;
                    if(a[p][q][trav] == '1'){
                        R[B[it].fi][B[it].se]=B[it];
 
                        trav ++ ;
                        las = mp(-1, -1);
                        while(a[p][q][trav] == '1'){
                            las = GG.back();
                            GG.pop_back();
                            trav ++ ;
                        }
                        if(las.fi == -1 && it > 0 && R[B[it - 1].fi][B[it - 1].se].fi != -1){
                            las = B[it - 1];
                            GG.pop_back();
                        }
                        if(las.fi != -1){
                            join(B[it], las);
                        }
                        GG.push_back(B[it]);
                    }
                    else{
                    }
                    trav ++ ;
                }
            }
        }
 
        for(int ii = 0; ii < 2 * n + 1; ii ++ ){
            for(int jj = 0; jj < 2 * n + 1; jj ++ ){
                if(jj + 1 < 2 * n + 1){
                    if(join(mp(ii, jj), mp(ii, jj + 1))) total -- ;
                }
                if(ii + 1 < 2 * n + 1){
                    if(join(mp(ii, jj), mp(ii + 1, jj))) total -- ;
                }
            }
        }
 
        return make_number(total);
    }
}

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:210:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  210 |             for(int p = 0 ;p < lis.size(); p ++ ){
      |                            ~~^~~~~~~~~~~~
mars.cpp:231:46: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  231 |                             while(ids.size() > q){
      |                                   ~~~~~~~~~~~^~~
mars.cpp:278:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  278 |                 for(int it = 0 ; it < B.size() ;it ++ ){
      |                                  ~~~^~~~~~~~~~

• 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: 24 / 24
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11