Submission #953491

#	Time	Username	Problem	Language	Result	Execution time	Memory
953491		weakweakweak	Council (JOI23_council)	C++17	41 / 100	4082 ms	7508 KiB

council

//target : 41 pts
#include <bits/stdc++.h>
using namespace std;

int cnt[21] = {0};
int n, k, a[310000] = {0}, half, ans[310000] = {0};

void solve2() {
    for (int i = 1; i <= n; i++) {
        int stable = 0;
        int nonstable = 0;
        for (int j = 0; j < k; j++) {
            if (a[i] & (1 << j)) cnt[j]--;
            if (cnt[j] >= half + 1) stable += (1 << j);
            else if (cnt[j] == half) nonstable += (1 << j);
        }
        int res = 0;
        for (int j = 1; j <= n; j++) {
            if (j == i) continue;
            int z = ((1 << k)-1 - a[j]) & nonstable;
            res = max(res, __builtin_popcount(z));
        }
        res += __builtin_popcount(stable);
        cout << res << '\n';
        for (int j = 0; j < k; j++) if (a[i] & (1 << j)) cnt[j]++;
    }
    exit(0);
}

void solve4 () {
    int qq[1000030] = {0};
    for (int i = 1; i <= n; i++) {
        int stable = 0;
        int nonstable = 0;
        for (int j = 0; j < k; j++) {
            if (a[i] & (1 << j)) cnt[j]--;
            if (cnt[j] >= half + 1) stable += (1 << j);
            else if (cnt[j] == half) nonstable += (1 << j);
        }
        int res = __builtin_popcount(stable) + qq[nonstable];
        ans[i] = max(ans[i], res);
        int rev = (1 << k) - 1 - a[i];
        for (int j = 0; j < (1 << k); j++) qq[j] = max(qq[j], __builtin_popcount(j & rev));
        for (int j = 0; j < k; j++) if (a[i] & (1 << j)) cnt[j]++;
    }
    memset(qq, 0, sizeof(qq));
    for (int i = n; i >= 1; i--) {
        int stable = 0;
        int nonstable = 0;
        for (int j = 0; j < k; j++) {
            if (a[i] & (1 << j)) cnt[j]--;
            if (cnt[j] >= half + 1) stable += (1 << j);
            else if (cnt[j] == half) nonstable += (1 << j);
        }
        int res = __builtin_popcount(stable) + qq[nonstable];
        ans[i] = max(ans[i], res);
        int rev = (1 << k) - 1 - a[i];
        for (int j = 0; j < (1 << k); j++) qq[j] = max(qq[j], __builtin_popcount(j & rev));
        for (int j = 0; j < k; j++) if (a[i] & (1 << j)) cnt[j]++;
    }
    for (int i = 1; i <= n; i++) cout << ans[i] << '\n';
    exit(0);
}

int main () {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 0, b; j < k; j++) {
            cin >> b;
            cnt[j] += b;
            a[i] += (1 << j) * b;
        }
    }
    half = (n) / 2;

    if (n <= 3000) {
        solve2();
    }
    if (k <= 14) {
        solve4();
    }
return 0;}

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