제출 #1281989

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281989		SamueleVid	화성 (APIO22_mars)	C++20	100 / 100	555 ms	5640 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(), 0);
        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;
        }
        reverse(num_base_5.begin(), num_base_5.end());

        // 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 quali sono 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;
            continue;
        }
        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 senza componente
    int comps_num = (2 * N + 1) * (2 * N + 1) + 2; // parto alto per essere safe
    for (int i = 0; i < 2 * N + 1; i ++) {
        for (int j = 0; j < 2 * N + 1; j ++) {

			// ignora gli zeri e gli elementi che hanno già una componente (>1)
            if (grid[i][j] == 1) {
                grid[i][j] = comps_num;
                comps_num ++;
            }
        }
    }
    
    dsu comps(comps_num + 3); // + epsilon per essere safe

    // unisco i quadratini adiacenti
    for (int i = 0; i < 2 * N; i ++) {
        for (int j = 0; j < 2 * N + 1; 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 + 1; i ++) {
        for (int j = 0; j < 2 * N; j ++) {
            if (grid[i][j] && grid[i][j + 1]) {
                comps.merge(grid[i][j], grid[i][j + 1]);
            }
        }
    } 

    // rinomino allo stesso modo i quadratini che fanno parte della stessa componente
    for (int i = 0; i < 2 * N + 1; i ++) {
        for (int j = 0; j < 2 * N + 1; j ++) {
            grid[i][j] = comps.boss(grid[i][j]);
        }
    }

}

string process(vector<vector<string>> a, int i, int j, int k, int N) {
    
    // Nel quadrato (0, m) x (0, m) mi salvo le seguenti informazioni
    // - i quadrati "interni" al quadrato (quindi esclusi i bordi in basso e a destra) li lascio uguali
    // - nei quadrati sul bordo in basso a destra, esclusi i vertici NE e SO, salvo la diagonale che parte
    // dal quadrato e prosegue fino in fondo, andando verso SE. Essendo 2 * N + 1 < 100, mi posso salvare
    // tutti i valori della diagonale senza problemi
    // - nel vertice NE (e simmetricamente per quello SO) del quadrato mi salvo rispettivamente:
    // 1) negli ultimi 9 bit il numero di isole che stanno sotto alla diagonale che parte dal quadrato e 
    // prosegue fino in fondo, andando verso SE. Queste isole si trovano all'interno del triangolo in basso a sinistra.
    // 2) nei primi 91 bit mi salvo la diagonale che parte dal quadrato e prosegue fino in fondo, andando verso SE e
    // a che componente fanno parte i quadrati sulla diagonale. In decode_components è spiegato come comprimo il tutto in 91 bits.

    // A ogni fase k > 0, si può costruire il nuovo vertice NE o SE partendo dalle diagonali e vertice precedenti,
    // dato che queste informazioni insieme vanno a costituire una nuova "diagonale grossa", spessa 3 quadrati,
    // che permette di calcolare nuove isole e nuove connessioni ed estendere il triangolo verso l'alto.

    // All'ultima fase k = N - 1 si uniscono i triangoli SO e NE con le diagonali centrali, e ciò permette
    // di calcolare il numero completo di isole, che verrà salvato nel primo quadrato.

    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) {
        // ultima fase

        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 + 1][b + 2] = (a[1][2][b] == '1') ? 1 : 0;
        }
        for (int b = 0; 2 + b < 2 * N + 1; b ++) {
            grid[b + 2][b + 1] = (a[2][1][b] == '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]);

        if (k != 0) {
            vector<int> diag_sotto = decode_components(a[2][0]);
            for (int b = 0; 2 + b < 2 * N + 1; b ++) {
                grid[2 + b][b] = diag_sotto[b];
            }

            // le componenti della diagonale sopra le shifto di max_calc_sotto elementi più in alto,
            // così non si confondono con le componenti della diagonale sotto
            int max_calc_sotto = 0;
            for (auto x : diag_sotto) max_calc_sotto = max(max_calc_sotto, x);

            vector<int> diag_sopra = decode_components(a[0][2]);
            for (int b = 0; 2 + b < 2 * N + 1; b ++) {
                grid[b][2 + b] = diag_sopra[b] + (diag_sopra[b] ? max_calc_sotto : 0);
            }
        }
        else {
            // prima iterazione : inserisco il quadratino così com'è
            grid[2][0] = (a[2][0][0] == '1') ? 1 : 0;
            grid[0][2] = (a[0][2][0] == '1') ? 1 : 0;
        }

        // calcola le componenti connesse, aggiornando il numero di isole
        calc_comps(grid, islands, i - j, N);

        set<int> visited_comps;

        for (int i = 0; i < 2 * N + 1; i ++) {
            for (int j = 0; j < 2 * N + 1; 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
        grid[i + 0][j + 0] = (a[0][0][0] == '1') ? 1 : 0;
        grid[i + 1][j + 0] = (a[1][0][0] == '1') ? 1 : 0;
        grid[i + 1][j + 1] = (a[1][1][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]);
            for (int b = 0; 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] == '1') ? 1 : 0;
        }

        // calcola le componenti connesse, aggiornando il numero di isole
        calc_comps(grid, islands, i - j, N);

        // e aggiorna le componenti
        vector<int> new_diag_sotto(2 * N + 1);
        for (int b = 0; i + b < 2 * N + 1; b ++) new_diag_sotto[b] = grid[i + 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 + 1; i ++) {
            for (int j = 0; j < 2 * N + 1; 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
        grid[i + 0][j + 0] = (a[0][0][0] == '1') ? 1 : 0;
        grid[i + 0][j + 1] = (a[0][1][0] == '1') ? 1 : 0;
        grid[i + 1][j + 1] = (a[1][1][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]);
            for (int b = 0; 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] == '1') ? 1 : 0;
        }

        // calcola le componenti connesse, aggiornando il numero di isole
        calc_comps(grid, islands, i - j, N);

        // e aggiorna le componenti
        vector<int> new_diag_sopra(2 * N + 1);
        for (int b = 0; j + b < 2 * N + 1; b ++) {
            new_diag_sopra[b] = grid[b][j + 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 + 1; i ++) {
            for (int j = 0; j < 2 * N + 1; 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 vertice 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 sul bordo precedente.
    }

    return diagonal;
}

• 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