oj.uz

Submission #751949

# Submission time Handle Problem Language Result Execution time Memory
751949 2023-06-01T23:32:34 Z grogu Council (JOI23_council) C++14
0 / 100
 65 ms 11948 KB 
#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};
  }
  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';
  }
}

Compilation message

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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 57 ms 8916 KB Output is correct
3 Incorrect 65 ms 11948 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 57 ms 8916 KB Output is correct
3 Incorrect 65 ms 11948 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 57 ms 8916 KB Output is correct
3 Incorrect 65 ms 11948 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 57 ms 8916 KB Output is correct
3 Incorrect 65 ms 11948 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -