Submission #889883

#	Time	Username	Problem	Language	Result	Execution time	Memory
889883		boris_mihov	Council (JOI23_council)	C++17	100 / 100	1171 ms	541724 KiB

council

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <cstring>
#include <vector>
#include <bitset>

typedef long long llong;
const int MAXN = 300000 + 10;
const int MAXB = (1 << 20);
const int MAXM = 21;

int n, m;
int a[MAXN];
int cntMask[MAXB];
llong comb[MAXM][MAXM];
llong up[MAXB][MAXM][2];
llong down[MAXB][MAXM];
llong cntDown[MAXB];
int cnt[MAXB];

int zero, one, two;

void solve()
{
    for (int i = 0 ; i < m ; ++i)
    {
        if (cnt[i] >= n / 2 + 2) two |= (1 << i);
        else if (cnt[i] == n / 2 + 1) one |= (1 << i);
        else if (cnt[i] == n / 2) zero |= (1 << i);
    }

    // std::cout << "zero: " << std::bitset <12> (zero).to_string() << '\n';
    // std::cout << "one : " << std::bitset <12> (one).to_string() << '\n';
    // std::cout << "two : " << std::bitset <12> (two).to_string() << '\n';

    for (int i = 0 ; i <= m ; ++i)
    {   
        comb[i][0] = 1; 
    }

    for (int i = 1 ; i <= m ; ++i)
    {
        for (int j = 1 ; j <= i ; ++j)
        {
            comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
        }
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        // std::cout << "increase: " << std::bitset <12> (((1 << m) - 1) ^ a[i]).to_string() << '\n';
        cntDown[((1 << m) - 1) ^ a[i]]++;
    }

    for (int mask = (1 << m) - 1 ; mask >= 0 ; --mask)
    {
        down[mask][m] = cntDown[mask];
        for (int bit = m - 1 ; bit >= 0 ; --bit)
        {
            if (mask & (1 << bit))
            {
                down[mask][bit] = down[mask][bit + 1];
            } else
            {
                down[mask][bit] = down[mask][bit + 1];
                down[mask][bit] += down[mask | (1 << bit)][bit + 1];
            }
        }
    }

    for (int mask = 0 ; mask < (1 << m) ; ++mask)
    {
        up[mask][0][m & 1] = down[mask][0];
    }

    
    for (int bit = m - 1 ; bit >= 0 ; --bit)
    {
        for (int mask = 0 ; mask < (1 << m) ; ++mask)
        {
            int myPop = __builtin_popcount(mask);
            // if (std::bitset <12> (mask).to_string() == "010001101110") std::cout << "count is: " << std::bitset <12> (mask).to_string() << " (" << myPop << ") = " << down[mask][0] << '\n';
            for (int pop = 0 ; pop <= myPop ; ++pop)
            {  
                up[mask][pop][bit & 1] = 0;
                if (mask & (1 << bit))
                {
                    if (pop > 0) up[mask][pop][bit & 1] += up[mask][pop - 1][(bit & 1) ^ 1];
                    up[mask][pop][bit & 1] += up[mask ^ (1 << bit)][pop][(bit & 1) ^ 1];
                } else
                {
                    up[mask][pop][bit & 1] = up[mask][pop][(bit & 1) ^ 1];
                }
            }
        }
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        int answer = __builtin_popcount(two | (one & (~a[i])));
        int mask = (one & a[i]) | (zero & (~a[i]));
        int myAnd = __builtin_popcount(mask & (~a[i]));
        // std::cout << "answer: " << answer << '\n';
        // std::cout << "mask: " << std::bitset <12> (mask).to_string()  << '\n';
        // std::cout << "curr: " << std::bitset <12> (~a[i]).to_string()  << '\n';
        // std::cout << "and&: " << std::bitset <12> ((~a[i]) & mask).to_string()  << '\n';

        for (int pop = m ; pop >= 0 ; --pop)
        {
            // std::cout << "add?: " << pop << ": " << up[mask][pop][0] << ' ' << comb[myAnd][pop] << '\n';
            if (up[mask][pop][0] > comb[myAnd][pop])
            {
                answer += pop;
                break;
            }
        }

        std::cout << answer << '\n';
    }
}

void input()
{   
    std::cin >> n >> m;
    for (int i = 1 ; i <= n ; ++i)
    {
        for (int bit = m - 1 ; bit >= 0 ; --bit)
        {
            int curr;
            std::cin >> curr;

            a[i] <<= 1;
            a[i] |= curr;
            cnt[bit] += curr;
        }
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    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