Submission #1147609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147609		fryingduc	Council (JOI23_council)	C++20	100 / 100	452 ms	27348 KiB

council

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

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 3e5 + 5;
const int MASK = (1 << 20) + 5;
int n, m;
bool b[maxn][21];
int a[maxn], cnt[21];
bool unused[21];
int maxr[maxn], tight[maxn];
int res[maxn];

using pii = pair<int, int>;
pair<pii, pii> f[MASK];
void upd(pair<pii, pii> &a, pair<int, int> b) {
  if (a.first.first > b.first) {
    if (b.second != a.first.second) {
      a.second = a.first;
    }
    a.first = b;
  } else if (a.second.first > b.first) {
    if (a.first.second != b.second) {
      a.second = b;
    }
  }
}

int check(int mask, int c) {
  int cnt = 0;
  for (int i = 0; i < m; ++i) {
    if((mask >> i & 1) and (c >> i & 1)) ++cnt;
  } 
  return cnt;
}

void solve() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < m; ++j) {
      cin >> b[i][j];
    }
  }
  int add = 0;
  for (int i = 0; i < m; ++i) {
    int sum = 0;
    for (int j = 1; j <= n; ++j) {
      sum += b[j][i];
    }
    if (sum - 2 >= n / 2) {
      ++add;
      unused[i] = 1;
    } else if (sum < n / 2) {
      unused[i] = 1;
    }
  }
  int new_m = 0;
  for (int j = 0; j < m; ++j) {
    if (unused[j]) continue;
    for (int i = 1; i <= n; ++i) {
      if (b[i][j]) {
        a[i] |= (1 << new_m);
        ++cnt[new_m];
      }
    }
    ++new_m;
  }
  m = new_m;
  memset(f, 0x3f, sizeof(f));
  for (int i = 1; i <= n; ++i) {
    int rv = ((1 << m) - 1) ^ a[i];
    if (!f[rv].first.first) {
      f[rv].second = make_pair(0, i);
    } else {
      f[rv].first = make_pair(0, i);
    }
  }
  for (int i = 0; i < m; ++i) {
    for (int mask = 0; mask < (1 << m); ++mask) {
      if (mask >> i & 1) continue;
      upd(f[mask], f[mask ^ (1 << i)].first);
      upd(f[mask], f[mask ^ (1 << i)].second);
    }
  }
  for (int mask = 0; mask < (1 << m); ++mask) {
    for (int i = 0; i < m; ++i) {
      if (mask >> i & 1) {
        pair<int, int> c = f[mask ^ (1 << i)].first; ++c.first;
        upd(f[mask], c);
        c = f[mask ^ (1 << i)].second; ++c.first;
        upd(f[mask], c);
      }
    }
  }
  for (int i = 0; i < m; ++i) {
    for (int mask = 0; mask < (1 << m); ++mask) {
      if (mask >> i & 1) continue;
      upd(f[mask], f[mask ^ (1 << i)].first);
      upd(f[mask], f[mask ^ (1 << i)].second);
    }
  }
  for (int i = 1; i <= n; ++i) {
    int max_res = 0;
    for (int j = 0; j < m; ++j) {
      cnt[j] -= (a[i] >> j & 1);
    }
    int mask = 0;
    for (int j = 0; j < m; ++j) {
      if (cnt[j] >= n / 2) {
        ++max_res;
        if ((cnt[j] - 1) < n / 2) {
          mask |= (1 << j);
        }
      }
    }
    maxr[i] = max_res;
    tight[i] = mask;
    int cur = f[mask].first.first;
    if (f[mask].first.second == i) {
      cur = f[mask].second.first;
    }
    debug(i, max_res, cur, mask, f[mask]);
    cout << add + max(0, max_res - cur) << '\n';
    for (int j = 0; j < m; ++j) {
      cnt[j] += (a[i] >> j & 1);
    }
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}
/*
3 4
0 0 0 0 
0 1 1 0
1 0 0 1
*/

• 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