Submission #1261217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261217		anteknne	Council (JOI23_council)	C++20	100 / 100	536 ms	20004 KiB

council

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false

const int MAXN = 300 * 1000 + 17;
const int MAXM = 20;
int suma[MAXM];
int a[MAXN];
int n, m;
pii dp[1 << MAXM][2];

void rob (int i, pii x) {
    if (dp[i][0].st < x.st) {
        pii y = dp[i][0];
        dp[i][0] = x;
        if (y.nd != dp[i][0].nd) {
            dp[i][1] = max(dp[i][1], y);
        }
    } else {
        if (x.nd != dp[i][0].nd) {
            dp[i][1] = max(dp[i][1], x);
        }
    }
}

int main () {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i ++) {
        int x = 0, y;
        for (int j = 0; j < m; j ++) {
            cin >> y;
            x += (y * (1 << j));
            if (y) {
                suma[j] ++;
            }
        }
        a[i] = x;
        x ^= ((1 << m) - 1);
        rob(x, {__builtin_popcount(x), i});
    }

    for (int i = (1 << m) - 1; i >= 0; i --) {
        for (int j = 0; j < m; j ++) {
            if (!((1 << j) & i)) {
                int x = i + (1 << j);
                rob(i, dp[x][0]);
                rob(i, dp[x][1]);
            }
        }
        dp[i][0].st = min(dp[i][0].st, __builtin_popcount(i));
        dp[i][1].st = min(dp[i][1].st, __builtin_popcount(i));
    }

    for (int i = 0; i < (1 << m); i ++) {
        for (int j = 0; j < m; j ++) {
            if (i & (1 << j)) {
                int x = i - (1 << j);
                rob(i, dp[x][0]);
                rob(i, dp[x][1]);
            }
        }
    }

    //cout << dp[4][0].st << " " << dp[4][0].nd << "\n";
    //cout << dp[4][1].st << " " << dp[4][1].nd << "\n";

    for (int i = 0; i < n; i ++) {
        int mask = 0;
        int wyn = 0;
        for (int j = 0; j < m; j ++) {
            int x = suma[j];
            if (a[i] & (1 << j)) {
                x --;
            }
            if (x == (n/2)) {
                mask += (1 << j);
            }
            if (x > n/2) {
                wyn ++;
            }
        }
        //cout << mask << "\n";
        //cout << dp[mask][0].st << " " << dp[mask][0].nd << "\n";
        if (dp[mask][0].nd != i) {
            cout << dp[mask][0].st + wyn << "\n";
        } else {
            cout << dp[mask][1].st + wyn << "\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