Submission #1147376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147376		ParsaGolestani	Council (JOI23_council)	C++20	100 / 100	528 ms	25676 KiB

council

#include <bits/stdc++.h>
using namespace std;

const int N = 300000;
const int M = 20;
const int INF = 1000000000;

int n, m;
int val[N + 10], sum[M + 10];
int mnIdx[(1 << M) + 10], mxIdx[(1 << M) + 10];
int mn1[(1 << M) + 10], mn2[(1 << M) + 10];
bool a[N + 10][M + 3];

void readInput() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            sum[j] += a[i][j];
            val[i] |= (a[i][j] * (1 << j));
        }
}

void calcMinMaxIdx() {
    for (int mask = 0; mask < (1 << m); mask++) {
        mnIdx[mask] = INF;
        mxIdx[mask] = -INF;
    }
    for (int i = 1; i <= n; i++) {
        int mask = ((1 << m) - 1) - val[i];
        mnIdx[mask] = min(mnIdx[mask], i);
        mxIdx[mask] = max(mxIdx[mask], i);
    }
    for (int j = 0; j < m; j++)
        for (int mask = (1 << m) - 1; mask >= 0; mask--)
            if ((mask & (1 << j)) == 0) {
                int newMask = mask + (1 << j);
                mnIdx[mask] = min(mnIdx[mask], mnIdx[newMask]);
                mxIdx[mask] = max(mxIdx[mask], mxIdx[newMask]);
            }
}

int counter(int idx, int mask) {
    return __builtin_popcount(val[idx] & mask);
}

void upd(pair<int, int> &p1, pair<int, int> &p2, int idx, int mask) {
    if (idx == p1.second || idx == p2.second)
        return;
    pair<int, int> tmp = {counter(idx, mask), idx};
    if (tmp < p2)
        p2 = tmp;
    if (p2 < p1)
        swap(p1, p2);
}

void calcMin1Min2() {
    for (int mask = 0; mask < (1 << m); mask++) {
        pair<int, int> p1, p2;
        p1 = p2 = {INF, INF};
        if (mnIdx[mask] != INF)
            p1 = {counter(mnIdx[mask], mask), mnIdx[mask]};
        if (mxIdx[mask] != -INF && mxIdx[mask] != mnIdx[mask])
            p2 = {counter(mxIdx[mask], mask), mxIdx[mask]};
        for (int j = 0; j < m; j++)
            if ((mask & (1 << j))) {
                int newMask = mask - (1 << j);
                if (mn1[newMask] != INF)
                    upd(p1, p2, mn1[newMask], mask);
                if (mn2[newMask] != INF)
                    upd(p1, p2, mn2[newMask], mask);
            }
        mn1[mask] = p1.second;
        mn2[mask] = p2.second;
    }
}

void calcAns(int idx) {
    int mask = 0, good = 0;
    for (int i = 0; i < m; i++) {
        int tmp = sum[i] - a[idx][i];
        if (tmp >= n / 2) {
            good++;
            if (tmp == n / 2)
                mask |= (1 << i);
        }
    }
    good -= (mn1[mask] == idx? counter(mn2[mask], mask): counter(mn1[mask], mask));
    cout << good << '\n';
}

void solve() {
    for (int i = 1; i <= n; i++)
        calcAns(i);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    calcMinMaxIdx();
    calcMin1Min2();
    solve();
    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