Submission #1147155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147155		lto5	Council (JOI23_council)	C++20	100 / 100	572 ms	24120 KiB

council

#include <bits/stdc++.h>

using namespace std;

int a[300005];
int ra[300005];
pair<int, int> f[1 << 20];
pair<int, int> g[1 << 20];
int pos[1 << 20];
int cnt[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 ".ans", "w", stdout);
  }
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < m; j++) {
      int x;
      cin >> x;
      cnt[j] += x;
      a[i] |= x << j;
    }
    ra[i] = a[i] ^ ((1 << m) - 1);
    pos[ra[i]]++;
    f[ra[i]] = {__builtin_popcount(ra[i]), ra[i]};
  }
  for (int i = 0; i < m; i++) {
    for (int mask = (1 << m) - 1; mask >= 0; mask--) {
      if ((mask >> i & 1) == 1) {
        continue;
      }
      array<pair<int, int>, 4> fs = {f[mask ^ (1 << i)], g[mask ^ (1 << i)], f[mask], g[mask]};
      fs[0].first--;
      fs[1].first--;
      sort(fs.begin(), fs.end(), greater<pair<int, int>>());
      f[mask] = fs[0];
      assert(f[mask].second == 0 or ((f[mask].second & mask) == mask));
      for (auto [u, v] : fs) {
        if (v != f[mask].second) {
          g[mask] = {u, v};
          break;
        }
      }
    }
  }
  for (int i = 0; i < m; i++) {
    for (int mask = 0; mask < 1 << m; mask++) {
      if ((mask >> i & 1) == 0) {
        continue;
      }
      array<pair<int, int>, 4> fs = {f[mask ^ (1 << i)], g[mask ^ (1 << i)], f[mask], g[mask]};
      sort(fs.begin(), fs.end(), greater<pair<int, int>>());
      f[mask] = fs[0];
      for (auto [u, v] : fs) {
        if (v != f[mask].second) {
          g[mask] = {u, v};
          break;
        }
      }
    }
  }
  int init = 0;
  for (int i = 1; i <= n; i++) {
    int ret = 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) {
        ret += cnt[k] - (a[i] >> k & 1) > n / 2;
      }
    }
    if (ra[i] != f[mask].second || pos[ra[i]] > 1) {
      ret += __builtin_popcount(mask & f[mask].second);
    } else if (ra[i] != g[mask].second || pos[ra[i]] > 1) {
      ret += __builtin_popcount(mask & g[mask].second);
    }
    cout << ret << "\n";
  }
  return 0;
}

Compilation message (stderr)

council.cpp: In function 'int main()':
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 ".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
council.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     freopen(task ".ans", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• 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