Submission #1051744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051744		MilosMilutinovic	Brought Down the Grading Server? (CEOI23_balance)	C++14	0 / 100	115 ms	141768 KiB

balance

#include <bits/stdc++.h>

using namespace std;

const int N = (int) (1e6) + 100;

int ptr[N], from[N], to[N];
vector<int> g[N];
vector<int> euler;
bool was[N];

void dfs(int v) {
  while (ptr[v] < (int) g[v].size()) {
    int e = g[v][ptr[v]];
    if (was[e]) {
      ptr[v] += 1;
      continue;
    }
    int u = (from[e] ^ to[e] ^ v);
    was[e] = true;
    ptr[v] += 1;
    dfs(u);
  }
  euler.push_back(v);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, s, t;
  cin >> n >> s >> t;
  vector<vector<int>> a(n, vector<int>(s));
  vector<vector<int>> pos(t);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < s; j++) {
      cin >> a[i][j];
      --a[i][j];
      pos[a[i][j]].push_back(i);
    }
  }
  vector<int> f(t);
  iota(f.begin(), f.end(), 0);
  for (int i = 0; i < t; i++) {
    if ((int) pos[i].size() > s) {
      t += 1;
      pos.push_back({});
      f.push_back(i);
      for (int j = s; j < (int) pos[i].size(); j++) {
        int v = pos[i].back();
        if ((int) pos.back().size() < s) {
          pos.back().push_back(v);
        } else {
          t += 1;
          pos.push_back({});
          f.push_back(i);
          pos.back().push_back(v);
        }
        pos[i].pop_back();
      }
    }
  }
  vector<vector<int>> res(n, vector<int>(s, -1));
  function<void(int, int, vector<vector<int>>)> Solve = [&](int l, int r, vector<vector<int>> a) {
    if (l == r) {
      for (int i = 0; i < n; i++) {
        res[i][l] = a[i][0];
      }
      return;
    }
    int m = r - l + 1;
    /* vector<vector<int>> pos(t);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        pos[a[i][j]].push_back(i);
      }
    } */
    for (int i = 0; i < n + t; i++) {
      g[i].clear();
      ptr[i] = 0;
    }
    int p = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        from[p] = i;
        to[p] = n + a[i][j];
        g[i].push_back(p);
        g[n + a[i][j]].push_back(p);
        p += 1;
      }
    }
    for (int i = 0; i < p; i++) {
      was[i] = false;
    }
    euler.clear();
    for (int i = 0; i < n; i++) {
      if (ptr[i] < (int) g[i].size()) {
        dfs(i);
      }
    }
    vector<vector<int>> L(n);
    vector<vector<int>> R(n);
    int sz = (int) euler.size();
    for (int i = 0; i < sz; i += 2) {
      if (i + 1 < sz) {
        L[euler[i]].push_back(euler[i + 1] - n);
      }
      if (i > 0) {
        R[euler[i]].push_back(euler[i - 1] - n);
      }
    }
    int mid = (l + r) >> 1;
    Solve(l, mid, L);
    Solve(mid + 1, r, R);
  };
  Solve(0, s - 1, a);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < s; j++) {
      cout << f[res[i][j]] + 1 << " ";
    }
    cout << '\n';
  }
  return 0; 
}

• 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