Submission #1228630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228630		LaMatematica14	Brought Down the Grading Server? (CEOI23_balance)	C++20	15 / 100	154 ms	42932 KiB

balance

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

vector<array<long long, 3>> euler(vector<vector<array<long long, 2>>> &adj) {
    long long n = adj.size();
    queue<long long> st;
    vector<bool> vis(n, 0);
    vector<long long> ind(n, 0);
    unordered_set<long long> used;
    vector<array<long long, 3>> ris;
    for (long long i = 0; i < n; i++) {
        if (adj[i].size() %2) st.push(i);
    }
    function<void(long long)> dfs = [&](long long a) {
        vis[a] = 1;
        for (long long &t = ind[a]; t < adj[a].size();) {
            t++;
            if (used.count(adj[a][t-1][1])) continue;
            used.insert(adj[a][t-1][1]);
            ris.push_back({a, adj[a][t-1][0], adj[a][t-1][1]});
            dfs(adj[a][t-1][0]);
        }
    };
    while (!st.empty()) {
        if (!vis[st.front()]) dfs(st.front());
        st.pop();
    }
    for (long long  i = 0; i < n; i++) {
        if (vis[i]) continue;
        dfs(i);
    }
    return ris;
} 

int main() {
    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];
    }

    function<void(long long, long long)> order = [&](long long l, long long r /* [) */) {
        if (l == r-1) return;
        long long mid = (l+r)/2;
        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});
        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*N+a});
                adj[comp[mat[i][a+mid-l]]].push_back({comp[mat[i][a]], i*N+a});
            }
        }
        vector<array<long long, 3>> ris = euler(adj);
        vector<long long> num(N, 0);
        for (auto x : ris) {
            x[2]/=N;
            mat[x[2]][l+num[x[2]]] = f[x[0]];
            mat[x[2]][mid+num[x[2]]] = f[x[1]];
            num[x[2]]++;
        }
        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: 0 / 15
• Subtask 3-2: 0 / 5
• Subtask 3-3: 0 / 5
• Subtask 4-1: 0 / 20
• Subtask 4-2: 0 / 10
• Subtask 4-3: 0 / 10