제출 #1160361

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160361		Perl32	Council (JOI23_council)	C++20	78 / 100	4091 ms	33704 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;
    if (m <= 17) {
        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];
        }
    } else {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                cin >> a[i][j];
                c[j] += a[i][j];
            }
        }
        const int need = n / 2;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) c[j] -= a[i][j];
            int mx = 0;
            for (int j = 0; j < n; ++j) {
                if (i == j) continue;
                for (int k = 0; k < m; ++k) c[k] -= a[j][k];
                int cur = 0;
                for (int k = 0; k < m; ++k) {
                    if (c[k] >= need) cur++;
                    c[k] += a[j][k];
                }
                mx = max(mx, cur);
            }
            for (int j = 0; j < m; ++j) c[j] += a[i][j];
            cout << mx << '\n';
        }
    }
}

/*

 */

• 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: 0 / 22