oj.uz

Submission #889880

# Submission time Handle Problem Language Result Execution time Memory
889880 2023-12-20T08:53:13 Z boris_mihov Council (JOI23_council) C++17
0 / 100
 2020 ms 1036064 KB 
#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];
__int128 comb[MAXM][MAXM];
__int128 up[MAXB][MAXM][2];
__int128 down[MAXB][MAXM];
__int128 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 - 1 ; 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 3 ms 12632 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2020 ms 1034924 KB Output is correct
6 Correct 1920 ms 1034896 KB Output is correct
7 Correct 1621 ms 1034896 KB Output is correct
8 Correct 1572 ms 1034964 KB Output is correct
9 Correct 1580 ms 1036064 KB Output is correct
10 Correct 1626 ms 1034776 KB Output is correct
11 Correct 1561 ms 1034960 KB Output is correct
12 Correct 1589 ms 1036056 KB Output is correct
13 Incorrect 1 ms 6492 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 3 ms 12632 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2020 ms 1034924 KB Output is correct
6 Correct 1920 ms 1034896 KB Output is correct
7 Correct 1621 ms 1034896 KB Output is correct
8 Correct 1572 ms 1034964 KB Output is correct
9 Correct 1580 ms 1036064 KB Output is correct
10 Correct 1626 ms 1034776 KB Output is correct
11 Correct 1561 ms 1034960 KB Output is correct
12 Correct 1589 ms 1036056 KB Output is correct
13 Incorrect 1 ms 6492 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 45 ms 9496 KB Output is correct
3 Correct 42 ms 9552 KB Output is correct
4 Correct 29 ms 8896 KB Output is correct
5 Correct 46 ms 9560 KB Output is correct
6 Incorrect 30 ms 8796 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 45 ms 9496 KB Output is correct
3 Correct 42 ms 9552 KB Output is correct
4 Correct 29 ms 8896 KB Output is correct
5 Correct 46 ms 9560 KB Output is correct
6 Incorrect 30 ms 8796 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 45 ms 9496 KB Output is correct
3 Correct 42 ms 9552 KB Output is correct
4 Correct 29 ms 8896 KB Output is correct
5 Correct 46 ms 9560 KB Output is correct
6 Incorrect 30 ms 8796 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 45 ms 9496 KB Output is correct
3 Correct 42 ms 9552 KB Output is correct
4 Correct 29 ms 8896 KB Output is correct
5 Correct 46 ms 9560 KB Output is correct
6 Incorrect 30 ms 8796 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 3 ms 12632 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2020 ms 1034924 KB Output is correct
6 Correct 1920 ms 1034896 KB Output is correct
7 Correct 1621 ms 1034896 KB Output is correct
8 Correct 1572 ms 1034964 KB Output is correct
9 Correct 1580 ms 1036064 KB Output is correct
10 Correct 1626 ms 1034776 KB Output is correct
11 Correct 1561 ms 1034960 KB Output is correct
12 Correct 1589 ms 1036056 KB Output is correct
13 Incorrect 1 ms 6492 KB Output isn't correct
14 Halted 0 ms 0 KB -