Submission #1281227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281227		SamueleVid	화성 (APIO22_mars)	C++20	0 / 100	0 ms	3196 KiB

mars

#include <bits/stdc++.h>
using namespace std;
#define ll long long

struct dsu {
    vector<int> p;
    vector<int> size;

    dsu(int N) {
        p.resize(N);
        iota(p.begin(), p.end(), 1);
        size.assign(N, 1);
    }

    int boss(int u) {
        if (p[u] == u) return u;
        return p[u] = boss(p[u]);
    }

    void merge(int a, int b) {
        a = boss(a);
        b = boss(b);
        if (size[a] < size[b]) swap(a, b);
        size[a] += size[b];
        p[b] = a; 
    }
};

int get_islands(string s) {
    // negli ultimi 9 bit mi salvo il numero di componenti. 
    // Sto considerando le componenti sotto (o sopra) la diagonale, che ha come upperbound
    // (2N + 1)(2N + 1) / 4 = 420, nel caso della scacchiera. Questo numero sta in 9 bit perché è minore di 2^9 = 512.

    int islands = 0;
    for (int i = 0; i < 9; i ++) {
        if (s[100 - 1 - i] == '1') islands += (1 << i);
    }

    return islands;
}

vector<int> decode_components(string s) {
    // In 91 bit mi salvo le componenti dei quadratini sulla diagonale. 
    // Le componenti formano una sorta di stringa di parentesi:
    // questo perché tutti i nodi stanno su una linea, le connessioni si trovano su un semipiano e il grafo è planare.
    // Quindi ogni quadratino può essere scritto come uno tra questi simboli: 
    // o : 0 il quadratino è acqua
    // (. : 1 
    // . : 2
    // .) : 3
    // (.) : 4
    // Essendo 5 simboli, per comprimerli bene, invece di tenermi 3 bits per ognuno, prendo
    // 3 simboli consecutivi, li converto in base 5 e poi li converto in binario. 
    // Questo mi fa usare 7 bit per 3 quadratini invece di 9. 
    // Dato che la lunghezza più lunga della diagonale che mi interessa è (2N + 1 - 2) = 39.
    // Quindi mi bastano 39 * 7 / 3 = 91 bits per salvarmi le componenti sulla diagonale.
    
    vector<int> parenthesis;

    for (int b = 0; b < 91; b += 7) {
        // converto 7 bits in un numero
        int num = 0;
        for (int i = 0; i < 7; i ++) {
            if (s[b + i] == '1') num += (1 << i);
        }

        // converto questo numero in base 5 (di 3 cifre)
        vector<int> num_base_5;
        for (int c = 0; c < 3; c ++) {
            num_base_5.push_back(num % 5);
            num /= 5;
        }

        // ogni numero in base 5 corrisponde a uno dei 5 simboli della stringa di parentesi
        for (auto x : num_base_5) parenthesis.push_back(x);
    }

    vector<int> comps;

    int next_comp = 2; // inizio con 2 così lascio da parte gli 0 (vuoti) e gli 1 (ancora senza comps)
    stack<int> curr_comp;
    for (auto x : parenthesis) {
        if (x == 0) { // o
            comps.push_back(0);
        }
        if (x == 1) { // (.
            curr_comp.push(next_comp);
            next_comp ++;
            comps.push_back(curr_comp.top());
        }
        if (x == 2) { // .
            comps.push_back(curr_comp.top());
        }
        if (x == 3) { // .)
            comps.push_back(curr_comp.top());
            curr_comp.pop();
        }
        if (x == 4) { // (.)
            curr_comp.push(next_comp);
            next_comp ++;
            comps.push_back(curr_comp.top());
            curr_comp.pop();
        }
    }

    return comps;
}

string encode_components(vector<int> comps, int islands) {

    // mi salvo l'inizio e la fine di ogni gruppo per capire come vanno le parentesi
    map<int, int> inizio;
    map<int, int> fine;
    for (int i = 0; i < comps.size(); i ++) {
        if (comps[i] == 0) continue;
        if (!inizio.count(comps[i])) inizio[comps[i]] = i;
        fine[comps[i]] = max(fine[comps[i]], i);
    }

    // scrivo le parentesi
    vector<int> parenthesis(39, 0);
    for (int i = 0; i < comps.size(); i ++) {
        if (comps[i] == 0) { // o
            parenthesis[i] = 0;
        }
        if (inizio[comps[i]] == i && fine[comps[i]] == i) { // (.
            parenthesis[i] = 1; 
        }
        if (inizio[comps[i]] != i && fine[comps[i]] != i) { // .
            parenthesis[i] = 2;
        }
        if (inizio[comps[i]] != i && fine[comps[i]] == i) { // .)
            parenthesis[i] = 3;
        }
        if (inizio[comps[i]] == i && fine[comps[i]] == i) { // (.)
            parenthesis[i] = 4;
        }
    }

    string s;
    // alla fine del ciclo s sarà lunga 91 caratteri
    for (int p = 0; p < 39; p += 3) {
        // trasformo una sequenza contigua di tre simboli in un numero in base 5
        
        int num = 0;
        for (int c = 0; c < 3; c ++) {
            num *= 5;
            num += parenthesis[p + c];       
        }

        // ricopio il numero in binario su una substring lunga 7 in s
        for (int i = 0; i < 7; i ++) {
            if ((1 << i) & num) s.push_back('1');
            else s.push_back('0');
        }
    }

    // codifico il numero di isole negli ultimi 9 bit di s.
    for (int i = 0; i < 9; i ++) s.push_back('0');

    for (int i = 0; i < 9; i ++) {
        if ((1 << i) & islands) s[100 - 1 - i] = '1';
    }

    return s;
}

void calc_comps(vector<vector<int>> &grid, int islands, int diag, int N) {
    
    // esplicita le varie componenti dei quadratini non sulla diagonale
    int comps_num = 2;
    for (int i = 0; i < 2 * N + 1 && i - diag < 2 * N + 1; i ++) {
        int j = i - diag;
        comps_num = max(comps_num, grid[i][j]);
    }

    comps_num ++;
    for (int i = 0; i < 2 * N; i ++) {
        for (int j = 0; j < 2 * N; j ++) {
            // ignora gli elementi sulla diagonale
            if (i - j == diag) continue;

            if (grid[i][j]) {
                grid[i][j] = comps_num;
                comps_num ++;
            }
        }
    }

    dsu comps(comps_num + 3); // + epsilon per essere sicuro

    for (int i = 0; i < 2 * N - 1; i ++) {
        for (int j = 0; j < 2 * N; j ++) {
            if (grid[i][j] && grid[i + 1][j]) {
                comps.merge(grid[i][j], grid[i + 1][j]);

            }
        }
    } 
    for (int i = 0; i < 2 * N; i ++) {
        for (int j = 0; j < 2 * N - 1; j ++) {
            if (grid[i][j] && grid[i][j + 1]) {
                comps.merge(grid[i][j], grid[i][j + 1]);
            }
        }
    } 

    for (int i = 0; i < 2 * N; i ++) {
        for (int j = 0; j < 2 * N; j ++) {
            grid[i][j] = comps.boss(grid[i][j]);
        }
    }
}

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) {
        // non è sul bordo quindi lo lascio uguale
        return a[0][0];
    }

    if (k == N - 1) {

        vector<vector<int>> grid(2 * N + 1, vector<int>(2 * N + 1));
        for (int y = 0; y < 2; y ++) {
            for (int x = 0; x < 2; x ++) {
                grid[y][x] = (a[y][x][0] == '1') ? 1 : 0;
            }
        }
        for (int b = 0; 2 + b < 2 * N + 1; b ++) {
            grid[b + 2][b + 2] = (a[2][2][b] == '1') ? 1 : 0;
        }

        int islands = get_islands(a[2][0]) + get_islands(a[0][2]);

        vector<int> diag_sotto = decode_components(a[2][0]);
        // la condizione (b < diag_sotto.size()) è inutile perché ha sempre 2 * N - 1 elementi, e quelli in eccesso sono segnati come 0 
        for (int b = 0; b < diag_sotto.size() && 2 + b < 2 * N + 1; b ++) {
            grid[2 + b][b] = diag_sotto[b];
        }

        vector<int> diag_sopra = decode_components(a[0][2]);
        // la condizione (b < diag_sotto.size()) è inutile perché ha sempre 2 * N - 1 elementi, e quelli in eccesso sono segnati come 0 
        for (int b = 0; b < diag_sopra.size() && 2 + b < 2 * N + 1; b ++) {
            grid[b][2 + b] = diag_sopra[b];
        }

        calc_comps(grid, islands, i - j, N);

        set<int> visited_comps;

        for (int i = 0; i < 2 * N; i ++) {
            for (int j = 0; j < 2 * N; j ++) {
                if (grid[i][j] == 0) continue;
                if (visited_comps.count(grid[i][j])) continue;
                islands ++;
                visited_comps.insert(grid[i][j]);
            }
        }

        // scrivo il numero di isole in binario nel risultato
        string s;
        for (int i = 0; i < 100; i ++) s.push_back('0');

        for (int p = 0; p < 20; p ++) {
            if ((1 << p) & islands) s[p] = '1';
        }

        return s;
    }

    if (j == 0) {
        // mi salvo le componenti nel triangolo in basso a sinistra

        vector<vector<int>> grid(2 * N + 1, vector<int>(2 * N + 1));
        
        // y < 2 ricopio i singoli punti
        for (int y = 0; y < 2; y ++) {
            for (int x = 0; x < 3; x ++) {
                grid[i + y][j + x] = (a[y][x][0] == '1') ? 1 : 0;
            }
        }

        // y = 2, x > 1 devo ricopiare le diagonali sotto
        for (int x = 1; x < 3; x ++) {
            for (int b = 0; i + 2 + b < 2 * N + 1; b ++) {
                grid[i + 2 + b][x + b] = (a[2][x][b] == '1') ? 1 : 0;
            }
        }

        int islands = get_islands(a[2][0]);

        if (k != 0) {
            vector<int> diag_sotto = decode_components(a[2][0]);
            // la condizione (b < diag_sotto.size()) è inutile perché ha sempre 2 * N - 1 elementi, e quelli in eccesso sono segnati come 0 
            for (int b = 0; b < diag_sotto.size() && i + 2 + b < 2 * N + 1; b ++) {
                grid[i + 2 + b][b] = diag_sotto[b];
            }
        }
        else {
            // prima iterazione : inserisco il quadratino così com'è
            grid[i + 2][j] = a[2][0][0];
        }

        // calcola le componenti connesse.
        calc_comps(grid, islands, i - j, N);

        // e aggiorna le componenti
        vector<int> new_diag_sotto(2 * N + 1);
        for (int b = 0; i + 2 + b < 2 * N + 1; b ++) new_diag_sotto[i] = grid[i + 2 + b][b];

        set<int> visited_comps;
        for (auto x : new_diag_sotto) {
            if (x != 0) visited_comps.insert(x);
        }

        for (int i = 0; i < 2 * N; i ++) {
            for (int j = 0; j < 2 * N; j ++) {
                if (grid[i][j] == 0) continue;
                if (visited_comps.count(grid[i][j])) continue;
                islands ++;
                visited_comps.insert(grid[i][j]);
            }
        }

        string res = encode_components(new_diag_sotto, islands);

        return res;
    }

    
    if (i == 0) {
        // mi salvo le componenti nel triangolo in alto a destra.
        // il codice è analogo a quello sopra

        vector<vector<int>> grid(2 * N + 1, vector<int>(2 * N + 1));
        
        // x < 2 ricopio i singoli punti
        for (int x = 0; x < 2; x ++) {
            for (int y = 0; y < 3; y ++) {
                grid[i + y][j + x] = (a[y][x][0] == '1') ? 1 : 0;
            }
        }

        // x = 2, y > 1 devo ricopiare le diagonali sotto
        for (int y = 1; y < 3; y ++) {
            for (int b = 0; j + 2 + b < 2 * N + 1; b ++) {
                grid[y + b][j + 2 + b] = (a[y][2][b] == '1') ? 1 : 0;
            }
        }

        int islands = get_islands(a[0][2]);

        if (k != 0) {
            vector<int> diag_sopra = decode_components(a[0][2]);
            // la condizione (b < diag_sotto.size()) è inutile perché ha sempre 2 * N - 1 elementi, e quelli in eccesso sono segnati come 0 
            for (int b = 0; b < diag_sopra.size() && j + 2 + b < 2 * N + 1; b ++) {
                grid[b][j + 2 + b] = diag_sopra[b];
            }
        }
        else {
            // prima iterazione : inserisco il quadratino così com'è
            grid[i][j + 2] = a[0][2][0];
        }

        // calcola le componenti connesse.
        calc_comps(grid, islands, i - j, N);

        // e aggiorna le componenti
        vector<int> new_diag_sopra(2 * N + 1);
        for (int b = 0; i + 2 + b < 2 * N + 1; b ++) new_diag_sopra[i] = grid[i + 2 + b][b];

        set<int> visited_comps;
        for (auto x : new_diag_sopra) {
            if (x != 0) visited_comps.insert(x);
        }

        for (int i = 0; i < 2 * N; i ++) {
            for (int j = 0; j < 2 * N; j ++) {
                if (grid[i][j] == 0) continue;
                if (visited_comps.count(grid[i][j])) continue;
                islands ++;
                visited_comps.insert(grid[i][j]);
            }
        }

        string res = encode_components(new_diag_sopra, islands);

        return res;
    }

    // se è sui bordi però non è il triangolo (ne o so) allora semplicemente mi salvo la diagonale

    // parte dal primo carattere e poi scende piano piano in basso a destra
    string diagonal = a[0][0]; // comincia copiando il primo punto (e anche il resto vuoto, così è lungo 100)
    diagonal[1] = a[1][1][0]; // copio il secondo punto
    for (int b = 0; b + 2 < 100; b ++) {
        diagonal[b + 2] = a[2][2][b]; // ricopio la diagonale salvata in a[2][2], che era il bordo precedente.
    }

    // // max è 2n, max m è 2n - 2

    // the diagonal is (2n + 1 - m) bits long

    return diagonal;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 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