Submission #935441

#	Time	Username	Problem	Language	Result	Execution time	Memory
935441		juliany2	Council (JOI23_council)	C++17	100 / 100	1798 ms	53076 KiB

council

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

const int N = 3e5 + 7, M = 20;
int n, m;
int a[N][M], sum[M];
array<array<int, 2>, 2> dp[1 << M];

array<array<int, 2>, 2> mx(array<array<int, 2>, 2> &x, array<array<int, 2>, 2> &y) {
    vector<array<int, 2>> l = {x[0], x[1], y[0], y[1]};
    sort(all(l), greater<>());

    array<array<int, 2>, 2> res = {{{0, -1}, {0, -1}}};
    int pt = 0, seen = -1;
    for (auto &[x, i] : l) {
        if (seen == i || pt == 2)
            continue;

        res[pt] = {x, i};
        pt++, seen = i;
    }

    return res;
}

array<array<int, 2>, 2> mn(array<array<int, 2>, 2> &x, array<array<int, 2>, 2> &y) {
    vector<array<int, 2>> l = {x[0], x[1], y[0], y[1]};
    sort(all(l));

    array<array<int, 2>, 2> res = {{{(int) 1e9, -1}, {(int) 1e9, -1}}};
    int pt = 0, seen = -1;
    for (auto &[x, i] : l) {
        if (seen == i || pt == 2)
            continue;

        res[pt] = {x, i};
        pt++, seen = i;
    }

    return res;
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> n >> m;

    int t = (n % 2) ^ 1;

    for (int i = 0; i < (1 << m); i++) {
        if (t == 0)
            dp[i] = {{{0, -1}, {0, -1}}};
        else
            dp[i] = {{{(int) 1e9, -1}, {(int) 1e9, -1}}};
    }

    for (int i = 0; i < n; i++) {
        int mask = 0;
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];

            sum[j] += (a[i][j] == 0 ? -1 : 1);

            if (a[i][j] == t)
                mask += 1 << j;
        }

        array<array<int, 2>, 2> cur = {{{__builtin_popcount(mask), i}, {__builtin_popcount(mask), i}}};
        if (t == 0)
            dp[mask] = mx(dp[mask], cur);
        else
            dp[mask] = mn(dp[mask], cur);
    }

    for (int j = 0; j < m; j++) {
        for (int i = 0; i < (1 << m); i++) {
            if (i >> j & 1) {
                array<array<int, 2>, 2> cur = dp[i];
                cur[0][0]--, cur[1][0]--;

                if (t == 0) {
                    dp[i] = mx(dp[i], dp[i ^ (1 << j)]);
                    dp[i ^ (1 << j)] = mx(dp[i ^ (1 << j)], cur);
                }
                else {
                    dp[i] = mn(dp[i], dp[i ^ (1 << j)]);
                    dp[i ^ (1 << j)] = mn(dp[i ^ (1 << j)], cur);
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        int ans = 0, mask = 0;
        for (int j = 0; j < m; j++) {
            int cur = sum[j] - (a[i][j] == 0 ? -1 : 1);

            ans += cur > 0;
            if (cur == 0 || cur == 1)
                mask += 1 << j;
        }

        int val = (dp[mask][0][1] == i ? dp[mask][1][0] : dp[mask][0][0]);

        cout << ans + (t == 0 ? 1 : -1) * val << '\n';
    }

    return 0;
}

• 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