Submission #784557

#	Time	Username	Problem	Language	Result	Execution time	Memory
784557		thimote75	Council (JOI23_council)	C++14	100 / 100	1443 ms	68648 KiB

council

#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;
using igrid = vector<idata>;

using pii = pair<int, int>;

int N, M;

void show_mask (int mask) {
    for (int i = 0; i < M; i ++)
        cout << (((1 << i) & mask) >> i);
}

struct MaskData {
    int maxsize = 0;
    pii n1 = { 0, - 1 };
    pii n2 = { 0, - 1 };

    void setMask (int i) {
        maxsize = 0;
        for (int u = 0; u < M; u ++)
            if ((1 << u) & i)
                maxsize ++;
    }
    int get (int node) {
        if (n1.second == node) return n2.first;
        return n1.first;
    }

    void append (int node, int size) {
        if (size > maxsize) size = maxsize;
        if (node == n1.second) {
            n1.first = max(size, n1.first);
            return ;
        }

        pii r = { size, node };
        if (r >= n1) {
            n2 = n1;
            n1 = r;
        } else if (r > n2) {
            n2 = r;
        }
    }
    void import (MaskData &other) {
        append(other.n1.second, other.n1.first);
        append(other.n2.second, other.n2.first);
    }
};

using vMD = vector<MaskData>;

idata sum;
igrid values;

vMD danger_mask;

int count (int mask) {
    int res = 0;

    for (int i = 0; i < M; i ++)
        if (mask & (1 << i))
            res ++;

    return res;
}

int main () {
    cin >> N >> M;

    sum.resize(M);
    values.resize(N, idata(M));

    danger_mask.resize(1 << M);

    for (int i = 0; i < danger_mask.size(); i ++)
        danger_mask[i].setMask(i);

    for (int i = 0; i < N; i ++) {
        for (int j = 0; j < M; j ++) {
            int x; cin >> x; x = 2 * x - 1;

            values[i][j] = x;
            sum[j] += x;
        }
    }

    for (int i = 0; i < N; i ++) {
        int dm = 0;
        int si = 0;
        for (int j = 0; j < M; j ++) {
            if (values[i][j] == 1) continue ;

            dm |= 1 << j;
            si ++;
        }

        danger_mask[dm].append(i, si);
    }

    for (int m = (1 << M) - 1; m >= 0; m --) {
        for (int h = 0; h < M; h ++) {
            int nm = (1 << h) | m;
            if (nm == m) continue ;

            danger_mask[m].import(danger_mask[nm]);
        }
    }

    for (int m = 0; m < danger_mask.size(); m ++) {
        for (int h = 0; h < M; h ++) {
            int nm = (1 << h) | m;
            if (nm == m) continue ;

            danger_mask[nm].import(danger_mask[m]);
        }
    }

    for (int i = 0; i < N; i ++) {
        int dm = 0;
        int si = 0;
        for (int j = 0; j < M; j ++) {
            int r = sum[j] - values[i][j];

            if (r >= 2) si ++;
            else if (r >= 0) dm |= (1 << j);
        }

        cout << danger_mask[dm].get(i) + si << endl;
    }
}

Compilation message (stderr)

council.cpp: In function 'int main()':
council.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<MaskData>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for (int i = 0; i < danger_mask.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~
council.cpp:114:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<MaskData>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for (int m = 0; m < danger_mask.size(); m ++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~

• 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