Submission #1073243

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073243		NeroZein	Brought Down the Grading Server? (CEOI23_balance)	C++17	50 / 100	355 ms	130648 KiB

balance

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

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

const int N = 5e5 + 5;

bool vis[N];
int original[N * 2];
vector<pair<int, int>> g[N];
vector<pair<int, int>> occ[N * 2];

void dfs(int v, vector<array<int, 3>>& lx, vector<array<int, 3>>& rx) {
  while (!g[v].empty()) {
    auto [i, u] = g[v].back();
    g[v].pop_back();
    if (vis[i]) {
      continue;
    }
    vis[i] = true; 
    if (v < u) {
      rx.push_back({i, v, u});
    } else {
      lx.push_back({i, u, v});
    }
    dfs(u, lx, rx); 
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, s, t;
  cin >> n >> s >> t;
  vector<vector<int>> a(n, vector<int> (s));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < s; ++j) {
      cin >> a[i][j];
      occ[a[i][j]].push_back({i, j});
    }
  }
  int cnt = t + 1; 
  for (int i = 1; i <= t; ++i) {
    original[i] = i;
    while ((int) occ[i].size() > s) {
      for (int j = 0; j < s; ++j) {
        auto [x, y] = occ[i].back();
        occ[i].pop_back();
        debug(x, y, cnt);
        a[x][y] = cnt;
      }
      original[cnt] = i;
      cnt++;
    }
  }
  //for (int i = 0; i < n; ++i) {
    //for (int j = 0; j < s; ++j) {
      //cout << a[i][j] << " \n"[j == s - 1];
    //}
  //}
  vector<array<int, 3>> edges; 
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < s; ++j) {
      edges.push_back({i * s + j, i, a[i][j] + n});
    }
  }
  vector<vector<int>> b(n, vector<int> (s));
  function<void(int, int, vector<array<int, 3>>)> solve = [&](int l, int r, vector<array<int, 3>> e) {
    if (l == r) {
      for (auto [i, row, task] : e) {
        b[row][l] = original[task - n];
      }
      return;
    }
    int mid = (l + r) >> 1;
    for (auto [i, u, v] : e) {
      vis[i] = false; 
      g[u].push_back({i, v});
      g[v].push_back({i, u});
    }
    vector<array<int, 3>> lx, rx; 
    for (auto [i, u, v] : e) {
      if (!vis[i]) {
        dfs(u, lx, rx);
      }
    }
    solve(l, mid, lx);
    solve(mid + 1, r, rx);
  };
  solve(0, s - 1, edges);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < s; ++j) {
      cout << b[i][j] << " \n"[j == s - 1]; 
    }
  }
  return 0;
}

• 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