답안 #966144

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
966144	2024-04-19T12:27:01 Z	abczz	Council (JOI23_council)	C++14	6 / 100	577 ms	51040 KB

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]) 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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-