Submission #727529

#	Time	Username	Problem	Language	Result	Execution time	Memory
727529		cig32	Council (JOI23_council)	C++17	100 / 100	1324 ms	111676 KiB

council

#include "bits/stdc++.h"
#define int long long
using namespace std;
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  int a[n][m];
  int b[n];
  int s[m];
  for(int i=0; i<m; i++) s[i] = 0;
  for(int i=0; i<n; i++) {
    b[i] = 0;
    for(int j=0; j<m; j++) {
      cin >> a[i][j];
      s[j] += a[i][j];
      b[i] |= (a[i][j] << j);
    }
  }
  int cnt[(1<<m)];
  int ans[(1<<m)];
  for(int i=0; i<(1<<m); i++) cnt[i] = 0, ans[i] = -1;
  for(int i=0; i<n; i++) cnt[b[i]]++;
  pair<int,int> dp[(1<<m)][2];
  for(int i=0; i<(1<<m); i++) for(int j=0; j<2; j++) dp[i][j] = {1e9, -1};
  for(int i=0; i<n; i++) {
    if(dp[b[i]][0].first == 0) dp[b[i]][1] = {0, i};
    else dp[b[i]][0] = {0, i};
  }
  for(int i=0; i<m; i++) {
    for(int j=0; j<(1<<m); j++) {
      if(j & (1<<i)) {
        vector<pair<int,int> > w = {
          dp[j^(1<<i)][0], dp[j^(1<<i)][1],
          dp[j][0], dp[j][1]
        };
        sort(w.begin(),w.end());
        dp[j][0] = w[0];
        for(int k=1; k<4; k++) {
          if(dp[j][0].second != w[k].second) {
            dp[j][1] = w[k]; break;
          }
        }
      }
    }
  }
  reverse(dp, dp+(1<<m));
  for(int i=1; i<(1<<m); i++) {
    if(dp[i][1].first == 0) continue;
    for(int j=0; j<m; j++) {
      if(i&(1<<j)) {
        int tar0=dp[i^(1<<j)][0].first+1, tar1=dp[i^(1<<j)][1].first+1;
        vector<pair<int,int> > w = {
          {tar0,dp[i^(1<<j)][0].second},
          {tar1,dp[i^(1<<j)][1].second},
          dp[i][0],dp[i][1]
        };
        sort(w.begin(), w.end());
        dp[i][0] = w[0];
        for(int k=1; k<4; k++) {
          if(dp[i][0].second != w[k].second) {
            dp[i][1] = w[k]; break;
          }
        }
      }
    }
  }
  for(int i=0; i<n; i++) {
    int bad = 0, base = 0;
    for(int j=0; j<m; j++) {
      int ss = s[j] - a[i][j];
      if(ss >= n/2) base++;
      if(ss == n/2) bad |= (1<<j);
    }
    int opt = dp[bad][0].first;
    if(dp[bad][0].second == i) opt = dp[bad][1].first;
    cout << base - opt << '\n';
  }
}
/*
g++ B.cpp -std=c++17 -o B
g++ B2.cpp -std=c++17 -o B2
g++ gen.cpp -std=c++17 -o gen
g++ checker.cpp -std=c++17 -o checker
for ((i=1; ; ++i)); do  
  ./gen $i > input_file
  ./B < input_file > myAnswer
  ./B2 < input_file > correctAnswer
  ./checker > checker_log
  echo "Passed test: " $i
done
*/

Compilation message (stderr)

council.cpp: In function 'int32_t main()':
council.cpp:22:7: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
   22 |   int ans[(1<<m)];
      |       ^~~

• 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