Submission #1160360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160360		Perl32	Council (JOI23_council)	C++20	62 / 100	4094 ms	41288 KiB

council

//I wrote this code 4 u <3
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

constexpr int inf = 0x3f3f3f3f;

const int maxN = 300'300;
const int maxM = 20;

int c[maxM], a[maxN][maxM];

signed main(int32_t argc, char *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    int sz = (1 << m);
    vector<vector<int>> kek(sz);
    for (int i = 0; i < n; ++i) {
        int x = 0;
        for (int j = 0, pw = 1; j < m; ++j, pw <<= 1) {
            cin >> a[i][j];
            c[j] += a[i][j];
            x += pw * a[i][j];
        }
        kek[x].push_back(i);
    }
    vector<array<int, 2>> mn(sz, {inf, -1}), smn(sz, {inf, -1});
    auto apply = [&](int id, const array<int, 2>& x) {
        if (mn[id] > x) {
            if (x[1] != mn[id][1]) {
                smn[id] = mn[id];
            }
            mn[id] = x;
        } else if (smn[id] > x && x[1] != mn[id][1]) {
            smn[id] = x;
        }
    };
    auto upd = [&](int id, int cnt, int from) {
        for (int i = 0; i < min(2, (int) kek[from].size()); ++i) {
            apply(id, {cnt, kek[from][i]});
        }
    };
    const int mx = sz - 1;
    for (int msk = 0; msk < sz; ++msk) {
        int rev = mx ^ msk;
        upd(rev, 0, msk);
        for (int sub = msk; sub; sub = (sub - 1) & msk) {
            int cnt = __builtin_popcount(sub);
            upd(rev | sub, cnt, msk);
        }
    }
    for (int msk = 0; msk < sz; ++msk) {
        for (int sub = msk; sub; sub = (sub - 1) & msk) {
            apply(sub, mn[msk]); apply(sub, smn[msk]);
        }
    }
    const int need = n / 2;
    for (int i = 0; i < n; ++i) {
        int msk = 0, cnt = 0;
        for (int j = 0, pw = 1; j < m; ++j, pw <<= 1) {
            c[j] -= a[i][j];
            if (c[j] == need) msk += pw;
            if (c[j] >= need) cnt++;
        }
        int res = -1;
        if (mn[msk][1] != -1 && mn[msk][1] != i) res = mn[msk][1];
        else if (smn[msk][1] != -1 && smn[msk][1] != i) res = smn[msk][1];
        for (int j = 0; j < m; ++j) {
            if (c[j] == need && a[res][j]) cnt--;
        }
        cout << cnt << '\n';
        for (int j = 0; j < m; ++j) c[j] += a[i][j];
    }
}

/*

 */

• Subtask 1: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 6 / 6
• Subtask 4: 19 / 19
• Subtask 5: 15 / 15
• Subtask 6: 22 / 22
• Subtask 7: 0 / 22