제출 #1146694

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146694		lto5	Council (JOI23_council)	C++20	100 / 100	574 ms	28308 KiB

council

#include <bits/stdc++.h>

using namespace std;

int a[300005];
int ra[300005];
int best[1 << 20];
pair<int, int> f[1 << 20];
pair<int, int> g[1 << 20];
int pos[1 << 20];

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.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 mask = 0; mask < 1 << m; mask++) {
    best[mask] = 1e9;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < m; j++) {
      int x;
      cin >> x;
      a[i] |= x << j;
    }
    ra[i] = a[i] ^ ((1 << m) - 1);
    pos[ra[i]]++;
    best[ra[i]] = 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];
      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;
  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 (ra[i] != f[mask].second || pos[ra[i]] > 1) {
      int cur = __builtin_popcount(mask) - __builtin_popcount(mask & f[mask].second);
      best = min(best, cur);
    }
    if (ra[i] != g[mask].second || pos[ra[i]] > 1) {
      int cur = __builtin_popcount(mask) - __builtin_popcount(mask & g[mask].second);
      best = min(best, cur);
    }
    cout << ret - best << "\n";
  }
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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