oj.uz

Submission #889878

# Submission time Handle Problem Language Result Execution time Memory
889878 2023-12-20T08:52:35 Z boris_mihov Council (JOI23_council) C++17
0 / 100
 822 ms 527880 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];
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 - 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 8536 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 772 ms 525660 KB Output is correct
6 Correct 783 ms 519816 KB Output is correct
7 Correct 790 ms 523848 KB Output is correct
8 Correct 797 ms 527880 KB Output is correct
9 Correct 775 ms 527824 KB Output is correct
10 Correct 822 ms 525936 KB Output is correct
11 Correct 807 ms 525764 KB Output is correct
12 Correct 776 ms 527824 KB Output is correct
13 Incorrect 2 ms 8536 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 8536 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 772 ms 525660 KB Output is correct
6 Correct 783 ms 519816 KB Output is correct
7 Correct 790 ms 523848 KB Output is correct
8 Correct 797 ms 527880 KB Output is correct
9 Correct 775 ms 527824 KB Output is correct
10 Correct 822 ms 525936 KB Output is correct
11 Correct 807 ms 525764 KB Output is correct
12 Correct 776 ms 527824 KB Output is correct
13 Incorrect 2 ms 8536 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 8540 KB Output is correct
2 Correct 41 ms 10256 KB Output is correct
3 Correct 48 ms 10324 KB Output is correct
4 Correct 30 ms 10324 KB Output is correct
5 Correct 42 ms 10328 KB Output is correct
6 Incorrect 30 ms 10332 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 8540 KB Output is correct
2 Correct 41 ms 10256 KB Output is correct
3 Correct 48 ms 10324 KB Output is correct
4 Correct 30 ms 10324 KB Output is correct
5 Correct 42 ms 10328 KB Output is correct
6 Incorrect 30 ms 10332 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 8540 KB Output is correct
2 Correct 41 ms 10256 KB Output is correct
3 Correct 48 ms 10324 KB Output is correct
4 Correct 30 ms 10324 KB Output is correct
5 Correct 42 ms 10328 KB Output is correct
6 Incorrect 30 ms 10332 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 8540 KB Output is correct
2 Correct 41 ms 10256 KB Output is correct
3 Correct 48 ms 10324 KB Output is correct
4 Correct 30 ms 10324 KB Output is correct
5 Correct 42 ms 10328 KB Output is correct
6 Incorrect 30 ms 10332 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 8536 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 772 ms 525660 KB Output is correct
6 Correct 783 ms 519816 KB Output is correct
7 Correct 790 ms 523848 KB Output is correct
8 Correct 797 ms 527880 KB Output is correct
9 Correct 775 ms 527824 KB Output is correct
10 Correct 822 ms 525936 KB Output is correct
11 Correct 807 ms 525764 KB Output is correct
12 Correct 776 ms 527824 KB Output is correct
13 Incorrect 2 ms 8536 KB Output isn't correct
14 Halted 0 ms 0 KB -