Submission #1051888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051888		MilosMilutinovic	Brought Down the Grading Server? (CEOI23_balance)	C++14	100 / 100	669 ms	143696 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;
    dfs(u);
    ptr[v] += 1;
  }
  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));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < s; j++) {
      cin >> a[i][j];
      --a[i][j];
    }
  }
  /* for (int i = 0; i < n; i++) {
    for (int j = 0; j < s; j++) {
      cout << a[i][j] << " ";
    }
    cout << endl;
  }
  cout << "t = " << t << endl; */
  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 + 1 + t; i++) {
      g[i].clear();
      ptr[i] = 0;
    }
    int p = 0;
    for (int i = 0; i < t; i++) {
      if ((int) pos[i].size() % 2 == 1) {
        from[p] = n;
        to[p] = n + 1 + i;
        g[n].push_back(p);
        g[n + 1 + i].push_back(p);
        p += 1;
      }
    }
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        from[p] = i;
        to[p] = n + 1 + a[i][j];
        g[i].push_back(p);
        g[n + 1 + a[i][j]].push_back(p);
        p += 1;
      }
    }
    for (int i = 0; i < p; i++) {
      was[i] = false;
    }
    vector<vector<int>> L(n);
    vector<vector<int>> R(n);
    for (int i = 0; i < n + 1; i++) {
      if (ptr[i] < (int) g[i].size()) {
        euler.clear();
        dfs(i);
        int sz = (int) euler.size();
        for (int i = 0; i < sz; i += 2) {
          if (euler[i] == n) {
            continue;
          }
          if (i + 1 < sz) {
            L[euler[i]].push_back(euler[i + 1] - n - 1);
          }
          if (i > 0) {
            R[euler[i]].push_back(euler[i - 1] - n - 1);
          }
        }
      }
    }
    /* if (l == 0 && r == 1) {
      cout << "euler = ";
      for (int i : euler) {
        cout << i << " ";
      }
      cout << endl;
    } */
    /* if (l == 0 && r == s - 1) {
      cout << "L" << endl;
      for (int i = 0; i < n; i++) {
        for (int v : L[i]) {
          cout << v << " ";
        }
        cout << endl;
      }
      cout << "R" << endl;
      for (int i = 0; i < n; i++) {
        for (int v : L[i]) {
          cout << v << " ";
        }
        cout << endl;
      } 
    } */
    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 << res[i][j] + 1 << " ";
    }
    cout << '\n';
  }
  return 0; 
}

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