Submission #794977

#	Time	Username	Problem	Language	Result	Execution time	Memory
794977		vjudge1	Council (JOI23_council)	C++17	100 / 100	1734 ms	30516 KiB

council

#include <bits/stdc++.h>

#define fi first
#define se second

const int N = 300200;
const int mod = 1e9 + 7;

using namespace std;

int n;
int m;
int a[N];
int c[20];
pair<int, int> d[1 << 20];
pair<int, int> f[1 << 20];

void comb(int mask, vector<pair<int, int>> v)
{
    v.push_back(d[mask]);
    v.push_back(f[mask]);
    sort(v.rbegin(), v.rend());

    d[mask] = v[0];
    f[mask] = {0, -2};
    for (int i = 1; i < v.size(); i++) {
        if (v[i].se != v[0].se) {
            f[mask] = v[i];
            break;
        }
    }
}

int main() {
    #ifdef zxc
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int x;
            cin >> x;
            a[i] |= (x << j);
            c[j] += x;
        }
    }

    for (int i = 0; i < (1 << m); i++) {
        d[i] = {0, -1};
        f[i] = {0, -2};
    }
    for (int i = 0; i < n; i++) {
        int mask = a[i] ^ ((1 << m) - 1);
        comb(mask, {make_pair(__builtin_popcount(mask), i)});
    }
    for (int i = (1 << m) - 1; i > 0; i--) {
        for (int j = 0; j < m; j++) {
            if (i & (1 << j)) {
                d[i].fi -= 1;
                f[i].fi -= 1;
                comb(i ^ (1 << j), {d[i], f[i]});
                d[i].fi += 1;
                f[i].fi += 1;
            }
        }
    }
    for (int i = 0; i < (1 << m); i++) {
        for (int j = 0; j < m; j++) {
            if (i & (1 << j)) {
                continue;
            }
            comb(i ^ (1 << j), {d[i], f[i]});
        }
    }

    for (int i = 0; i < n; i++) {
        int mask = 0, res = 0;
        for (int j = 0; j < m; j++) {
            int g = (a[i] >> j) & 1;
            if (c[j] - g > n / 2) {
                res += 1;
            } else if (c[j] - g == n / 2) {
                mask |= (1 << j);
            }
        }

        cout << res + (d[mask].se == i ? f[mask].fi : d[mask].fi) << "\n";
    }
}

Compilation message (stderr)

council.cpp: In function 'void comb(int, std::vector<std::pair<int, int> >)':
council.cpp:26:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (int i = 1; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~

• 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