Submission #920288

#	Time	Username	Problem	Language	Result	Execution time	Memory
920288		andrei_iorgulescu	Council (JOI23_council)	C++14	100 / 100	2033 ms	60100 KiB

council

#include <bits/stdc++.h>

using namespace std;

int n,m;
int masca[300005];
vector<int>o[(1 << 20) + 5];
int fr[25],rfr[25];

int maskmare;

bool cmp(int x,int y)
{
    return __builtin_popcount(masca[x] & maskmare) > __builtin_popcount(masca[y] & maskmare);
}

vector<int> srt(vector<int>v, int mask)
{
    maskmare = mask;
    sort(v.begin(),v.end(),cmp);
    return v;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            char ch;
            cin >> ch;
            if (ch == '0')
                masca[i] += (1 << j);
            if (ch == '1')
                fr[j]++;
        }
    }
    for (int i = 1; i <= n; i++)
        o[masca[i]].push_back(i);
    for (int i = 0; i < (1 << m); i++)
        while (o[i].size() > 2)
            o[i].pop_back();
    for (int mask = (1 << m) - 1; mask >= 0; mask--)
    {
        for (int b = 0; b < m; b++)
        {
            if (!(mask & (1 << b)))
            {
                int msk = mask + (1 << b);
                for (int i = 0; i < o[msk].size(); i++)
                {
                    if (o[mask].size() == 0)
                        o[mask].push_back(o[msk][i]);
                    else if (o[mask].size() == 1 and o[mask][0] != o[msk][i])
                        o[mask].push_back(o[msk][i]);
                }
            }
        }
    }
    for (int mask = 0; mask < (1 << m); mask++)
    {
        for (int b = 0; b < m; b++)
        {
            if (mask & (1 << b))
            {
                int msk = mask - (1 << b);
                vector<int>vnou;
                vnou = o[mask];
                for (int i = 0; i < o[msk].size(); i++)
                {
                    bool rau = false;
                    for (int j = 0; j < vnou.size(); j++)
                        if (vnou[j] == o[msk][i])
                            rau = true;
                    if (!rau)
                        vnou.push_back(o[msk][i]);
                }
                o[mask] = srt(vnou,mask);
                while (o[mask].size() > 2)
                    o[mask].pop_back();
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        int curmask = 0;
        for (int j = 0; j < m; j++)
            rfr[j] = fr[j];
        for (int j = 0; j < m; j++)
            if (!(masca[i] & (1 << j)))
                rfr[j]--;
        int cate = 0;
        for (int j = 0; j < m; j++)
        {
            if (rfr[j] == n / 2)
                curmask += (1 << j);
            else if (rfr[j] > n / 2)
                cate++;
        }
        int cine = o[curmask][0];
        if (o[curmask][0] == i)
            cine = o[curmask][1];
        cout << cate + (int)(__builtin_popcount(masca[cine] & curmask)) << '\n';
    }
    return 0;
}

Compilation message (stderr)

council.cpp: In function 'int main()':
council.cpp:54:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |                 for (int i = 0; i < o[msk].size(); i++)
      |                                 ~~^~~~~~~~~~~~~~~
council.cpp:73:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |                 for (int i = 0; i < o[msk].size(); i++)
      |                                 ~~^~~~~~~~~~~~~~~
council.cpp:76:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |                     for (int j = 0; j < vnou.size(); j++)
      |                                     ~~^~~~~~~~~~~~~

• 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