Submission #894231

#	Time	Username	Problem	Language	Result	Execution time	Memory
894231		box	Council (JOI23_council)	C++17	100 / 100	524 ms	30672 KiB

council

#include "bits/stdc++.h"
using namespace std;
 
#define FOR(i, l, r) for (int i = (l); i < (r); i++)
#define F0R(i, n) FOR(i, 0, n)
#define ROF(i, l, r) for (int i = (r)-1; i >= l; i--)
#define R0F(i, n) ROF(i, 0, n)
 
#define ar array
#define sz(v) static_cast<int>(v.size())
#define all(v) begin(v), end(v)
typedef vector<int> vi;
typedef long long ll;
 
struct two {
  pair<int, int> v[2];
 
  two() { v[0] = v[1] = make_pair(20, -1); }
  void add(pair<int, int> p) {
    auto [x, i] = p;
    if (v[0].first > x)
      v[1] = v[0], v[0] = {x, i};
    else if (v[1].first > x)
      v[1] = {x, i};
  }
  int get(int i) {
    if (v[0].second != i) return v[0].first;
    return v[1].first;
  }
};
pair<int, int> ad(pair<int, int> p) {
  p.first++;
  return p;
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);
  const int N = 3e5, M = 20;
  int n, m;
  cin >> n >> m;
  static int bm[N];
  static int all[M];
  F0R(i, n) F0R(j, m) {
    int x;
    cin >> x;
    all[j] += x;
    bm[i] |= x << j;
  }
  static two f[1 << M];
  F0R(i, n) f[bm[i]].add({0, i});
  F0R(b, m) {
    int blk = 1 << b;
    for (int i = 0; i < 1 << m; i += 2 * blk) FOR(j, i, i + blk) {
        two u = f[j], v = f[j + blk];
        f[j] = f[j + blk] = two();
        f[j].add(u.v[0]);
        f[j].add(u.v[1]);
        f[j].add(v.v[0]);
        f[j].add(v.v[1]);
        f[j + blk].add(u.v[0]);
        f[j + blk].add(u.v[1]);
        f[j + blk].add(ad(v.v[0]));
        f[j + blk].add(ad(v.v[1]));
      }
  }
  int bound = n / 2;
  F0R(i, n) {
    F0R(j, m) if (bm[i] >> j & 1) all[j]--;
    int cnt = 0, b = 0;
    F0R(j, m)
    if (all[j] > bound)
      cnt++;
    else if (all[j] == bound)
      cnt++, b |= 1 << j;
    cout << cnt - f[b].get(i) << '\n';
    F0R(j, m) if (bm[i] >> j & 1) all[j]++;
  }
}

• 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