Submission #966239

#	Time	Username	Problem	Language	Result	Execution time	Memory
966239		abczz	Council (JOI23_council)	C++14	100 / 100	1022 ms	57796 KiB

council

#include <iostream>
#include <array>
#include <vector>
#define ll long long

using namespace std;

ll n, m, a, f, mask, cnt[20], A[300000];
vector <ll> V[21];
array <array<ll, 2>, 2> dp[(1LL<<20)];

void add(ll u, array<ll, 2> x) {
  if (dp[u][0][0] < x[0]) {
    if (dp[u][0][1] != x[1]) dp[u][1] = dp[u][0];
    dp[u][0] = x;
  }
  else if (dp[u][1][0] < x[0] && dp[u][0][1] != x[1]) dp[u][1] = x;
}
int main() {
  cin >> n >> m;
  for (int i=0; i<(1LL<<20); ++i) {
    dp[i] = {0, -1, 0, -1};
    V[__builtin_popcount(i)].push_back(i);
  }
  for (int i=0; i<n; ++i) {
    for (int j=0; j<m; ++j) {
      cin >> a;
      cnt[j] += a;
      A[i] += a<<j;
    }
    add(A[i] ^ (((1LL<<m)-1)), {__builtin_popcount(A[i] ^ ((1LL<<m)-1)), i});
  }
  for (int i=20; i>1; --i) {
    for (auto u : V[i]) {
      for (int j=0; j<20; ++j) {
        if (u & (1LL<<j)) {
          add(u-(1LL<<j), {dp[u][0][0]-1, dp[u][0][1]});
          add(u-(1LL<<j), {dp[u][1][0]-1, dp[u][1][1]});
        }
      }
    }
  }
  for (int i=1; i<20; ++i) {
    for (auto u : V[i]) {
      for (int j=0; j<20; ++j) {
        if (!(u & (1LL<<j))) {
          add(u+(1LL<<j), dp[u][0]);
          add(u+(1LL<<j), dp[u][1]);
        }
      }
    }
  }
  for (int i=0; i<n; ++i) {
    f = mask = 0;
    for (int j=0; j<20; ++j) {
      a = cnt[j]-(bool)(A[i] & (1LL<<j));
      if (a > n/2) ++f;
      else if (a == n/2) mask += (1LL<<j);
    }
    if (dp[mask][0][1] != i) f += dp[mask][0][0];
    else f += dp[mask][1][0];
    cout << f << '\n';
  }
}

• 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