Submission #751951

#	Time	Username	Problem	Language	Result	Execution time	Memory
751951		grogu	Council (JOI23_council)	C++14	100 / 100	1310 ms	110908 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 j=0;j<m;j++) {
        for(int i = 1;i<(1<<m);i++) {
          if(dp[i][1].first == 0) continue;
          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';
      }
    }

Compilation message (stderr)

council.cpp: In function 'int32_t main()':
council.cpp:22:11: 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