Submission #1146579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146579		lto5	Council (JOI23_council)	C++20	6 / 100	414 ms	16908 KiB

council

#include <bits/stdc++.h>

using namespace std;

int a[300005];
pair<int, int> f[1 << 20];
pair<int, int> g[1 << 20];
int cnt[20];
int cnt_value[1 << 20];

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
#define task "a"
  if (fopen(task ".inp", "r")) {
    freopen(task ".inp", "r", stdin);
    freopen(task ".out", "w", stdout);
  }
  int n, m;
  cin >> n >> m;
  for (int mask = 0; mask < 1 << m; mask++) {
    f[mask] = {1e9, 1e9};
    g[mask] = {1e9, 1e9};
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < m; j++) {
      int x;
      cin >> x;
      a[i] |= x << j;
    }
    cnt_value[a[i]]++;
    f[a[i]] = {__builtin_popcount(a[i]), a[i]};
  }
  for (int mask = 0; mask < 1 << m; mask++) {
    for (int i = 0; i < m; i++) {
      if ((mask >> i & 1) == 0) {
        continue;
      }
      array<pair<int, int>, 4> fs = {f[mask ^ (1 << i)], g[mask ^ (1 << i)], f[mask], g[mask]};
      if (fs[0].first != 1e9) {
        fs[0].first = __builtin_popcount(fs[0].second & mask);
      }
      if (fs[1].first != 1e9) {
        fs[1].first = __builtin_popcount(fs[1].second & mask);
      }
      sort(fs.begin(), fs.end());
      f[mask] = fs[0];
      for (auto [u, v] : fs) {
        if (v != f[mask].second) {
          g[mask] = {u, v};
          break;
        }
      }
    }
  }
  for (int mask = (1 << m) - 1; mask >= 0; mask--) {
    for (int i = 0; i < m; i++) {
      if ((mask >> i & 1) == 1) {
        continue;
      }
      array<pair<int, int>, 4> fs = {f[mask ^ (1 << i)], g[mask ^ (1 << i)], f[mask], g[mask]};
      if (fs[0].first != 1e9) {
        fs[0].first = __builtin_popcount(fs[0].second & mask);
      }
      if (fs[1].first != 1e9) {
        fs[1].first = __builtin_popcount(fs[1].second & mask);
      }
      sort(fs.begin(), fs.end());
      f[mask] = fs[0];
      for (auto [u, v] : fs) {
        if (v != f[mask].second) {
          g[mask] = {u, v};
          break;
        }
      }
    }
  }
  int init = 0;
  vector<int> cnt(m, 0);
  for (int i = 1; i <= n; i++) {
    for (int k = a[i]; k > 0; k -= k & -k) {
      ++cnt[__builtin_ctz(k)];
    }
  }
  for (int i = 0; i < m; i++) {
    if (cnt[i] < n / 2) ++init;
  }
  for (int i = 1; i <= n; i++) {
    int aff = 0;
    int mask = 0;
    for (int k = 0; k < m; k++) {
      if (cnt[k] - (a[i] >> k & 1) == n / 2) {
        mask |= 1 << k;
      } else if (cnt[k] >= n / 2 && cnt[k] - (a[i] >> k & 1) < n / 2) {
        aff++;
      }
    }
    int ret = m - aff - init;
    int best = 1e9;
    if (f[mask].second != 1e9 && (a[i] != f[mask].second || cnt_value[a[i]] > 1)) {
      int cur = __builtin_popcount(mask & f[mask].second);
      best = min(best, cur);
    }
    if (g[mask].second != 1e9 && (a[i] != g[mask].second || cnt_value[a[i]] > 1)) {
      int cur = __builtin_popcount(mask & g[mask].second);
      best = min(best, cur);
    }
    cout << ret - best << "\n";
  }
  return 0;
}

Compilation message (stderr)

council.cpp: In function 'int main()':
council.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen(task ".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
council.cpp:17:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     freopen(task ".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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