Submission #1043721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043721		juicy	Council (JOI23_council)	C++17	62 / 100	224 ms	21900 KiB

council

// https://oj.uz/submission/767768 <3

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 3e5 + 5, MAX = 1e9;
const array<int, 2> inf = {MAX, MAX};

int n, m;
int a[N], cnt[20];
array<array<int, 2>, 2> f[N], g[N];

void add(array<array<int, 2>, 2> &x, array<int, 2> y) {
  for (auto it : x) {
    if (it[1] == y[1]) {
      return;
    }
  }
  if (y[0] < x[0][0]) {
    x[1] = x[0];
    x[0] = y;
  } else {
    x[1] = min(x[1], y);
  }
}

void upd(array<array<int, 2>, 2> &x, array<array<int, 2>, 2> y) {
  for (auto it : y) {
    add(x, it);
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> m;
  for (int i = 0; i < (1 << m); ++i) {
    f[i] = g[i] = {inf, inf};
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < m; ++j) {
      int x; cin >> x;
      a[i] += x << j;
      cnt[j] += x;
    }
    add(f[a[i]], {__builtin_popcount(a[i]), i});
  }
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < (1 << m); ++j) {
      if (!(j >> i & 1)) {
        upd(f[j], f[j ^ (1 << i)]);
      }
    }
  }
  for (int i = 0; i < (1 << m); ++i) {
    int cnt = __builtin_popcount(i);
    for (auto [x, it] : f[i]) {
      add(g[i], {x - cnt, it});
    }
  }
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < (1 << m); ++j) {
      if (j >> i & 1) {
        upd(g[j], g[j ^ (1 << i)]);
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    int mask = (1 << m) - 1, res = 0;
    for (int j = 0; j < m; ++j) {
      int c = a[i] >> j & 1;
      cnt[j] -= c;
      if (cnt[j] > n / 2) {
        ++res;
      } else if (cnt[j] == n / 2) {
        mask ^= 1 << j;
        ++res;
      }
      cnt[j] += c;
    }
    for (auto [x, it] : g[mask]) {
      if (it != i) {
        res -= x;
        break;
      }
    }
    cout << res << "\n";
  }
  return 0;
}

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