Submission #777729

#	Time	Username	Problem	Language	Result	Execution time	Memory
777729		tch1cherin	Council (JOI23_council)	C++17	100 / 100	2675 ms	35140 KiB

council

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

const int N = 20, C = sqrt(300000);
int c[2][1 << (N / 2)][1 << (N / 2)], ans[1 << N] = {}, cnt[N] = {};
vector<int> go[2][1 << (N / 2)];
int occ[1 << N] = {}, a[1 << N];

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  auto fhalf = [](int x) { return x & ((1 << (N / 2)) - 1); };
  auto shalf = [](int x) { return x >> (N / 2); };
  auto concat = [](int x, int y) { return (x << (N / 2)) + y; };
  for (int i = 0; i < n; i++) {
    int mask = 0;
    for (int j = 0; j < m; j++) {
      int x;
      cin >> x;
      if (x == 1) {
        cnt[j]++;
      }
      mask += x << j;
    }
    occ[mask]++;
    go[0][fhalf(mask)].push_back(shalf(mask));
    go[1][shalf(mask)].push_back(fhalf(mask));
    a[i] = mask;
  }
  for (int i = 0; i < (1 << (N / 2)); i++) {
    for (int j = 0; j < 2; j++) {
      sort(go[0][i].begin(), go[0][i].end());
      go[0][i].resize(unique(go[0][i].begin(), go[0][i].end()) - go[0][i].begin());
    }
  }
  for (int i = 0; i < (1 << (N / 2)); i++) {
    for (int j = 0; j < (1 << (N / 2)); j++) {
      for (int k = 0; k < N / 2; k++) {
        if (cnt[k] - ((i >> k) & 1) - ((j >> k) & 1) < n / 2) {
          c[0][i][j]++;
        }
        if (cnt[k + N / 2] - ((i >> k) & 1) - ((j >> k) & 1) < n / 2) {
          c[1][i][j]++;
        }
      }
    }
  }
  fill(ans, ans + (1 << N), 2e9);
  for (int u = 0; u < (1 << (N / 2)); u++) {
    for (int v = 0; v < (1 << (N / 2)); v++) {
      int optX = 1e9, optY = 1e9;
      for (int w : go[0][u]) {
        if (w != v) {
          optX = min(optX, c[1][v][w]);
        }
      }
      for (int w : go[1][v]) {
        if (w != u) {
          optY = min(optY, c[0][u][w]);
        }
        int cc = concat(v, w);
        ans[cc] = min(ans[cc], c[0][u][w] + optX);
      }
      for (int w : go[0][u]) {
        int cc = concat(w, u);
        ans[cc] = min(ans[cc], c[1][v][w] + optY);
      }
      int CC = concat(v, u);
      if (occ[CC] > 1) {
        ans[CC] = min(ans[CC], c[0][u][u] + c[1][v][v]);
      }
    }
  }
  for (int i = 0; i < n; i++) {
    cout << max(0, N - ans[a[i]]) << "\n";
  }
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 19 / 19
• Subtask 5: 15 / 15
• Subtask 6: 22 / 22
• Subtask 7: 22 / 22