제출 #1211547

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1211547		jerzyk	Council (JOI23_council)	C++20	100 / 100	567 ms	18952 KiB

council

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1'000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1'000'000'007LL;
const int N = 1<<20;
pair<int, int> dp1[N], dp2[N];
int tab[N], il[N];

void Akt(int a, pair<int, int> cur)
{
    if(dp1[a] < cur) swap(dp1[a], cur);
    if(dp2[a] < cur && cur.nd != dp1[a].nd) swap(dp2[a], cur);
}

void Solve()
{
    int n, m, a;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 0; j < m; ++j)
        {
            cin >> a;
            il[j] += a;
            tab[i] += a * (1<<j);
        }
        a = tab[i] ^ ((1<<m) - 1);
        pair<int, int> cur = pair{__builtin_popcount(a), i};
        Akt(a, cur);
    }
    for(int i = (1<<m) - 1; i >= 0; --i)
    {
        for(int j = 0; j < m; ++j)
            if(((1<<j) & i) == 0)
            {
                a = (1<<j) | i;
                Akt(i, dp1[a]);
                Akt(i, dp2[a]);
            }
        a = __builtin_popcount(i);
        dp1[i].st = min(dp1[i].st, a);
        dp2[i].st = min(dp2[i].st, a);
    }
    for(int i = 0; i < (1<<m); ++i)
    {
        for(int j = 0; j < m; ++j)
            if((1<<j) & i)
            {
                a = (1<<j) ^ i;
                Akt(i, dp1[a]);
                Akt(i, dp2[a]);
            }
    }
    for(int i = 1; i <= n; ++i)
    {
        int ans = 0, cur = 0;
        for(int j = 0; j < m; ++j)
        {
            a = il[j] - (((1<<j) & tab[i]) / (1<<j));
            if(a > n / 2)
                ++ans;
            if(a == n / 2)
                cur += (1<<j);
        }
        //cout << "A: " << i << " " << ans << " " << dp1[cur].nd << " " << dp2[cur].nd << "\n";
        if(dp1[cur].nd != i)
            ans += dp1[cur].st;
        else
            ans += dp2[cur].st;
        cout << ans << "\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

• 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