Submission #1228665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228665		LaMatematica14	Brought Down the Grading Server? (CEOI23_balance)	C++20	50 / 100	759 ms	101044 KiB

balance

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

vector<array<long long, 3>> euler(vector<vector<array<long long, 2>>> &adj) {
    // funzione autoesplicativa, restituisce la lista di archi direzionati
    // con in ingresso la lista di adiecenza dei non direzionati
    long long n = adj.size(), aus = -1;
    queue<long long> st; // starting points dispari
    vector<bool> vis(n, 0); // controllo i nodi visitati (per componente conessa)
    vector<long long> ind(n, 0); //tengo gli indici per non riscorrere tutti gli archi nella dfs
    unordered_set<long long> used; //tengo gli archi usati per direzionare only once
    vector<array<long long, 3>> ris; //da restituire!!
    for (long long i = 0; i < n; i++) {
        if (adj[i].size() %2) st.push(i); // se il nodo ha numero di archi dispari deve essere un inizio o una fine
    }
    function<void(long long, long long)> dfs = [&](long long a, long long s) {
        if (!vis[a] && adj[a].size()%2) {
            adj[s].push_back({a, aus});
            adj[a].push_back({s, aus--});
        }
        vis[a] = 1; // visitato
        for (long long &t = ind[a]; t < adj[a].size();) {
            t++; // aumento il puntatore e non riconsidero l'arco
            // se ripasso nel nodo
            if (used.count(adj[a][t-1][1])) continue;
            used.insert(adj[a][t-1][1]); // l'arco e' stato direzionato
            ris.push_back({a, adj[a][t-1][0], adj[a][t-1][1]});
            dfs(adj[a][t-1][0], s); //continuo la dfs
        }
    };
    // itero su tutti gli inizi non gia' visitati
    while (!st.empty()) {
        if (!vis[st.front()]) dfs(st.front(), st.front());
        st.pop();
    }
    // itero su tutti gli altri nodi (componenti dove posso iniziare il tour dove voglio)
    for (long long  i = 0; i < n; i++) {
        if (vis[i]) continue;
        dfs(i, -1);
    }
    return ris;
} 

int main() {
    //ingresso di variabili e matrice
    long long N, S, T; cin >> N >> S >> T;
    vector<vector<long long>> mat(N, vector<long long> (S));
    for (long long i = 0; i < N; i++) {
        for (long long j = 0; j < S; j++) cin >> mat[i][j];
    }

    // funzione ricorsiva top-down per ordinare i segmenti successivamente
    function<void(long long, long long)> order = [&](long long l, long long r /* [) */) {
        if (l == r-1) return; // sono arrivata all'intervallo 1

        long long mid = (l+r)/2;
        
        //INDEX COMPRESSION
        vector<long long> f; 
        for (long long i = 0; i < N; i++) {
            for (long long a = l; a < r; a++) f.push_back(mat[i][a]);
        }
        sort(f.begin(), f.end()); f.erase(unique(f.begin(), f.end()), f.end());
        unordered_map<long long, long long> comp;
        for (long long i = 0; i < f.size(); i++) comp.insert({f[i], i});
        // ora ho un numero lineare di nodi invece che sempre T

        // creo la lista di adiacenza, con unique identifiers per
        // i multi-edges e ricordando in che riga era questo edge
        // gli archi sono fra parte sinistra e destra della riga centrale
        // a coppie ordinate
        vector<vector<array<long long, 2>>> adj(f.size());
        for (long long i = 0; i < N; i++) {
            for (long long a = l; a < mid; a++) {
                adj[comp[mat[i][a]]].push_back({comp[mat[i][a+mid-l]], i*S+a});
                adj[comp[mat[i][a+mid-l]]].push_back({comp[mat[i][a]], i*S+a});
            }
        }

        // prendo il risultato e lo rimetto nella matrice
        // tutti i primi vanno messi nella prima meta'
        // gli altri nella seconda
        vector<array<long long, 3>> ris = euler(adj);
        vector<long long> num(N, 0);
        for (auto x : ris) {
            if (x[2] < 0) continue;
            x[2]/= S;
            mat[x[2]][l+num[x[2]]] = f[x[0]];
            mat[x[2]][mid+num[x[2]]] = f[x[1]];
            num[x[2]]++;
        }

        // ricorro nei due segmenti sottostanti
        order(l, mid);
        order(mid, r);
    };

    order(0, S);
    cout << endl;
    for (long long i = 0; i < N; i++) {
        for (long long j = 0; j < S; j++) cout << mat[i][j] << " ";
        cout << "\n";
    }
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2-1: 15 / 15
• Subtask 2-2: 0 / 5
• Subtask 2-3: 0 / 5
• Subtask 3-1: 15 / 15
• Subtask 3-2: 0 / 5
• Subtask 3-3: 0 / 5
• Subtask 4-1: 20 / 20
• Subtask 4-2: 0 / 10
• Subtask 4-3: 0 / 10