Submission #1111678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111678		flashmt	Council (JOI23_council)	C++17	100 / 100	787 ms	123468 KiB

council

#include <bits/stdc++.h>
using namespace std;
const int M = 20;

vector<int> id[1 << M];

void dfs(int bit, int mask, int curId)
{
  if (size(id[mask]) >= 2)
    return;

  if (bit < 0)
  {
    id[mask].push_back(curId);
    return;
  }

  dfs(bit - 1, mask, curId);
  if (mask >> bit & 1)
    dfs(bit - 1, mask ^ 1 << bit, curId);
}

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> cntCol(m);
  vector<vector<int>> a(n, vector<int>(m));
  vector<int> maskA(n);
  for (int i = 0; i < n; i++)
  {
    int mask = 0;
    for (int j = 0; j < m; j++)
    {
      cin >> a[i][j];
      if (a[i][j]) cntCol[j]++;
      else mask |= 1 << j;
    }
    dfs(m - 1, mask, i);
  }

  vector<pair<int, int>> f(1 << m, make_pair(0, -1));
  auto f2 = f;
  for (int mask = 1; mask < 1 << m; mask++)
    if (!empty(id[mask]))
    {
      int bit = __builtin_popcount(mask);
      f[mask] = {bit, id[mask][0]};
      if (size(id[mask]) == 2)
        f2[mask] = {bit, id[mask][1]};
    }

  auto update = [&](pair<int, int> u, int mask)
  {
    if (u > f[mask])
    {
      if (f[mask].second != u.second)
        f2[mask] = f[mask];
      f[mask] = u;
    }
    else if (f[mask].second != u.second)
    {
      f2[mask] = max(f2[mask], u);
    }
  };

  for (int i = 0; i < m; i++)
    for (int mask = 1; mask < 1 << m; mask++)
      if (mask >> i & 1)
      {
        update(f[mask ^ 1 << i], mask);
        update(f2[mask ^ 1 << i], mask);
      }

  int need = n / 2;
  for (int i = 0; i < n; i++)
  {
    int importantMask = 0, approved = 0;
    for (int j = 0; j < m; j++)
    {
      cntCol[j] -= a[i][j];
      if (cntCol[j] == need) importantMask |= 1 << j;
      else if (cntCol[j] > need) approved++;
    }

    int best = f[importantMask].second != i ? f[importantMask].first : f2[importantMask].first;
    cout << approved + best << '\n';

    for (int j = 0; j < m; j++)
      cntCol[j] += a[i][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