Submission #1211085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211085		dima2101	Council (JOI23_council)	C++20	100 / 100	731 ms	38964 KiB

council

#include <bits/stdc++.h>
#define int long long

struct Node
{
    int first_max;
    int ind1;
    int second_max;
    int ind2;

    Node()
    {
        first_max = 0;
        ind1 = -1;
        second_max = 0;
        ind2 = -1;
    }
};

Node relax(Node now, std::pair<int, int> be)
{
    if (now.ind1 == -1 && be.second != now.ind1)
    {
        now.first_max = be.first;
        now.ind1 = be.second;
    }
    else if (now.first_max < be.first)
    {
        if (be.second != now.ind1)
        {
            now.second_max = now.first_max;
            now.ind2 = now.ind1;
        }

        now.first_max = be.first;
        now.ind1 = be.second;
    }
    else if (now.ind2 == -1 && be.second != now.ind1)
    {
        now.second_max = be.first;
        now.ind2 = be.second;
    }
    else if (now.second_max < be.first && be.second != now.ind1)
    {
        now.second_max = be.first;
        now.ind2 = be.second;
    }
    return now;
}

signed
main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n, m;
    std::cin >> n >> m;
    std::vector<int> all(n);
    std::vector<Node> dp((1 << m));
    for (int i = 0; i < n; i++)
    {
        int now = 0;
        for (int j = 0; j < m; j++)
        {
            int help;
            std::cin >> help;
            if (help == 1)
            {
                now |= (1 << j);
            }
        }
        all[i] = now;
        dp[now] = relax(dp[now], std::make_pair(m - __builtin_popcount(now), i));
    }

    for (int i = 0; i < (1 << m); i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (!((i >> j) & 1))
            {
                int help = i;
                help |= (1 << j);
                Node need = dp[i];
                need.first_max--;
                need.second_max--;
                dp[help] = relax(dp[help], std::make_pair(need.first_max, need.ind1));
                dp[help] = relax(dp[help], std::make_pair(need.second_max, need.ind2));
            }
        }
    }

    for (int i = (1 << m) - 1; i >= 0; i--)
    {
        for (int j = 0; j < m; j++)
        {
            if ((i >> j) & 1)
            {
                int help = i;
                help ^= (1 << j);
                dp[help] = relax(dp[help], std::make_pair(dp[i].first_max, dp[i].ind1));
                dp[help] = relax(dp[help], std::make_pair(dp[i].second_max, dp[i].ind2));
            }
        }
    }

    std::vector<int> type(m);
    for (int i = 0; i < m; i++)
    {
        int cnt = 0;
        for (int j = 0; j < n; j++)
        {
            if ((all[j] >> i) & 1)
            {
                cnt++;
            }
            else
            {
                cnt--;
            }
        }
        if (cnt < -1)
        {
            type[i] = -2;
        }
        else if (cnt == -1)
        {
            type[i] = -1;
        }
        else if (cnt == 0)
        {
            type[i] = -1;
        }
        else if (cnt == 1 || cnt == 2)
        {
            type[i] = 0;
        }
        else
        {
            type[i] = 1;
        }
        // std::cout << i << ' ' << type[i] << std::endl;
    }
    std::vector<int> ans(n);
    for (int i = 0; i < n; i++)
    {
        int ind = (1 << m) - 1;
        int cnt = 0;
        for (int j = 0; j < m; j++)
        {
            if (type[j] == 1)
            {
                cnt++;
                continue;
            }
            if ((all[i] >> j) & 1)
            {
                if (type[j] == 0)
                {
                    ind ^= (1 << j);
                }
            }
            else
            {
                if (type[j] == 0)
                {
                    cnt++;
                }
                if (type[j] == -1)
                {
                    ind ^= (1 << j);
                }
            }
        }
        // for (int j = 0; j < m; j++)
        // {
        //     if ((ind >> j) & 1)
        //     {
        //         std::cout << "0";
        //     }
        //     else
        //     {
        //         std::cout << "1";
        //     }
        // }
        // std::cout << std::endl;
        // std::cout << ind << ' ' << cnt << ' ' << dp[ind].first_max << std::endl;
        if (dp[ind].ind1 == i)
        {
            ans[i] = cnt + dp[ind].second_max;
        }
        else
        {
            ans[i] = cnt + dp[ind].first_max;
        }
    }
    for (int i = 0; i < n; i++)
    {
        std::cout << ans[i] << std::endl;
    }
    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