제출 #1228627

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228627		LaMatematica14	Brought Down the Grading Server? (CEOI23_balance)	C++20	0 / 100	106 ms	39820 KiB

balance

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

vector<array<long long, 3>> euler(vector<vector<array<long long, 2>>> &adj) {
    int n = adj.size();
    queue<int> st;
    vector<int> vis(n, 0);
    vector<int> ind(n, 0);
    unordered_set<long long> used;
    vector<array<long long, 3>> ris;
    for (int i = 0; i < n; i++) {
        if (adj[i].size() %2) st.push(i);
    }
    function<void(int)> dfs = [&](int a) {
        vis[a] = 1;
        for (int &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 (int  i = 0; i < n; i++) {
        if (vis[i]) continue;
        dfs(i);
    }
    return ris;
} 

int main() {
    int N, S, T; cin >> N >> S >> T;
    vector<vector<int>> mat(N, vector<int> (S));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < S; j++) cin >> mat[i][j];
    }

    function<void(int, int)> order = [&](int l, int r /* [) */) {
        if (l == r-1) return;
        int mid = (l+r)/2;
        vector<int> f;
        for (int i = 0; i < N; i++) {
            for (int 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<int, int> comp;
        for (int i = 0; i < f.size(); i++) comp.insert({f[i], i});
        vector<vector<array<long long, 2>>> adj(f.size());
        for (int i = 0; i < N; i++) {
            for (int 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<int> 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);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < S; j++) cout << mat[i][j] << " ";
        cout << "\n";
    }
}

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