oj.uz

Submission #966144

# Submission time Handle Problem Language Result Execution time Memory
966144 2024-04-19T12:27:01 Z abczz Council (JOI23_council) C++14
6 / 100
 577 ms 51040 KB 
#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]) 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 42780 KB Output is correct
2 Correct 212 ms 42776 KB Output is correct
3 Correct 202 ms 42948 KB Output is correct
4 Correct 215 ms 42776 KB Output is correct
5 Correct 197 ms 42776 KB Output is correct
6 Correct 200 ms 42960 KB Output is correct
7 Correct 227 ms 42780 KB Output is correct
8 Correct 227 ms 42780 KB Output is correct
9 Correct 240 ms 42956 KB Output is correct
10 Incorrect 218 ms 42808 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 42780 KB Output is correct
2 Correct 212 ms 42776 KB Output is correct
3 Correct 202 ms 42948 KB Output is correct
4 Correct 215 ms 42776 KB Output is correct
5 Correct 197 ms 42776 KB Output is correct
6 Correct 200 ms 42960 KB Output is correct
7 Correct 227 ms 42780 KB Output is correct
8 Correct 227 ms 42780 KB Output is correct
9 Correct 240 ms 42956 KB Output is correct
10 Incorrect 218 ms 42808 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 42948 KB Output is correct
2 Correct 287 ms 46860 KB Output is correct
3 Correct 296 ms 46652 KB Output is correct
4 Correct 252 ms 46100 KB Output is correct
5 Correct 295 ms 46864 KB Output is correct
6 Correct 265 ms 46068 KB Output is correct
7 Correct 305 ms 46632 KB Output is correct
8 Correct 200 ms 43028 KB Output is correct
9 Correct 200 ms 42768 KB Output is correct
10 Correct 194 ms 42780 KB Output is correct
11 Correct 195 ms 42948 KB Output is correct
12 Correct 193 ms 42776 KB Output is correct
13 Correct 198 ms 42780 KB Output is correct
14 Correct 218 ms 43020 KB Output is correct
15 Correct 205 ms 42944 KB Output is correct
16 Correct 195 ms 42776 KB Output is correct
17 Correct 206 ms 42964 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 42948 KB Output is correct
2 Correct 287 ms 46860 KB Output is correct
3 Correct 296 ms 46652 KB Output is correct
4 Correct 252 ms 46100 KB Output is correct
5 Correct 295 ms 46864 KB Output is correct
6 Correct 265 ms 46068 KB Output is correct
7 Correct 305 ms 46632 KB Output is correct
8 Correct 200 ms 43028 KB Output is correct
9 Correct 200 ms 42768 KB Output is correct
10 Correct 194 ms 42780 KB Output is correct
11 Correct 195 ms 42948 KB Output is correct
12 Correct 193 ms 42776 KB Output is correct
13 Correct 198 ms 42780 KB Output is correct
14 Correct 218 ms 43020 KB Output is correct
15 Correct 205 ms 42944 KB Output is correct
16 Correct 195 ms 42776 KB Output is correct
17 Correct 206 ms 42964 KB Output is correct
18 Correct 206 ms 42952 KB Output is correct
19 Correct 195 ms 42776 KB Output is correct
20 Correct 577 ms 50964 KB Output is correct
21 Incorrect 519 ms 51040 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 42948 KB Output is correct
2 Correct 287 ms 46860 KB Output is correct
3 Correct 296 ms 46652 KB Output is correct
4 Correct 252 ms 46100 KB Output is correct
5 Correct 295 ms 46864 KB Output is correct
6 Correct 265 ms 46068 KB Output is correct
7 Correct 305 ms 46632 KB Output is correct
8 Correct 200 ms 43028 KB Output is correct
9 Correct 200 ms 42768 KB Output is correct
10 Correct 194 ms 42780 KB Output is correct
11 Correct 195 ms 42948 KB Output is correct
12 Correct 193 ms 42776 KB Output is correct
13 Correct 198 ms 42780 KB Output is correct
14 Correct 218 ms 43020 KB Output is correct
15 Correct 205 ms 42944 KB Output is correct
16 Correct 195 ms 42776 KB Output is correct
17 Correct 206 ms 42964 KB Output is correct
18 Correct 206 ms 42952 KB Output is correct
19 Correct 195 ms 42776 KB Output is correct
20 Correct 577 ms 50964 KB Output is correct
21 Incorrect 519 ms 51040 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 42948 KB Output is correct
2 Correct 287 ms 46860 KB Output is correct
3 Correct 296 ms 46652 KB Output is correct
4 Correct 252 ms 46100 KB Output is correct
5 Correct 295 ms 46864 KB Output is correct
6 Correct 265 ms 46068 KB Output is correct
7 Correct 305 ms 46632 KB Output is correct
8 Correct 200 ms 43028 KB Output is correct
9 Correct 200 ms 42768 KB Output is correct
10 Correct 194 ms 42780 KB Output is correct
11 Correct 195 ms 42948 KB Output is correct
12 Correct 193 ms 42776 KB Output is correct
13 Correct 198 ms 42780 KB Output is correct
14 Correct 218 ms 43020 KB Output is correct
15 Correct 205 ms 42944 KB Output is correct
16 Correct 195 ms 42776 KB Output is correct
17 Correct 206 ms 42964 KB Output is correct
18 Correct 206 ms 42952 KB Output is correct
19 Correct 195 ms 42776 KB Output is correct
20 Correct 577 ms 50964 KB Output is correct
21 Incorrect 519 ms 51040 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 42780 KB Output is correct
2 Correct 212 ms 42776 KB Output is correct
3 Correct 202 ms 42948 KB Output is correct
4 Correct 215 ms 42776 KB Output is correct
5 Correct 197 ms 42776 KB Output is correct
6 Correct 200 ms 42960 KB Output is correct
7 Correct 227 ms 42780 KB Output is correct
8 Correct 227 ms 42780 KB Output is correct
9 Correct 240 ms 42956 KB Output is correct
10 Incorrect 218 ms 42808 KB Output isn't correct
11 Halted 0 ms 0 KB -