Submission #727415

#	Time	Username	Problem	Language	Result	Execution time	Memory
727415		model_code	Council (JOI23_council)	C++17	100 / 100	1373 ms	104344 KiB

council

#include <array>
#include <bitset>
#include <iostream>
#include <vector>
using namespace std;

constexpr int N_MAX = 3e5, M_MAX = 20;
int popcnt(int x) { return bitset<32>(x).count(); }
int read() {
    int x;
    scanf("%d", &x);
    return x;
}
int A[N_MAX], agree[M_MAX], sum[1 << M_MAX][M_MAX], mn[1 << M_MAX][2];
int main() {
    const int N = read(), M = read();

    // 入力・各案に何票あるか数える
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            const int x = read();
            A[i] |= x << j;
            agree[j] += x;
        }
    }

    // 可決に必要な票数
    const int need = N / 2;
    // need + 0 票の集合、need + 1 票の集合、need + 2 票以上の案の数
    int zero = 0, one = 0, two = 0;
    for(int i = 0; i < M; i++) {
        if(agree[i] == need) zero |= 1 << i;
        if(agree[i] == need + 1) one |= 1 << i;
        if(agree[i] >= need + 2) two++;
    }

    // sum[s][d] = 案の集合を s に絞ったとき、そのうち d 個に賛成している人の数
    for(int i = 0; i < N; i++) {
        const int a = A[i];
        sum[a][popcnt(a)]++;
    }
    // 高速ゼータ変換 (下位集合に累積和)
    for(int d = 0; d < M; d++) for(int s = 0; s < 1 << M; s++) if(s & 1 << d) {
                const int t = s ^ 1 << d, i = popcnt(s);
                sum[t][i - 1] += sum[s][i];
    }
    // 求めたいものを作る
    for(int d = 0; d < M; d++) for(int s = 0; s < 1 << M; s++) if(s & 1 << d) {
        const int t = s ^ 1 << d;
        for(int i = 0; i < M; i++) sum[s][i] += sum[t][i] - sum[s][i + 1];
    }
    // 各 s に対し d の first min, second min を求める
    for(int s = 0; s < 1 << M; s++) for(int d = M; d--; ) {
        if(sum[s][d] < 1) continue;
        if(sum[s][d] == 1) {
            mn[s][1] = mn[s][0];
            mn[s][0] = d;
        }
        else {
            mn[s][0] = d;
            mn[s][1] = d;
        }
    }
    // 各議員に対し答えを求める。
    for(int i = 0; i < N; i++) printf("%d\n", [&](int a) -> int {
        const int ZERO = (zero & ~a) | (one & a);
        const int rejected = mn[ZERO][mn[ZERO][0] == popcnt(a & ZERO)];
        return two + popcnt(one | ZERO) - rejected;
    }(A[i]));
}

Compilation message (stderr)

council.cpp: In function 'int read()':
council.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     scanf("%d", &x);
      |     ~~~~~^~~~~~~~~~

• 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