Submission #1161121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161121		ace5	Council (JOI23_council)	C++20	100 / 100	2473 ms	29052 KiB

council

#include <bits/stdc++.h>

using namespace std;

const int maxn = 300005,maxm = 21;

bool a[maxm][maxn];
pair<int,int> dp[1<<maxm];
int x[1<<maxm];
pair<int,int> mx[1<<maxm];
int cou[maxm];
int tnum[maxn];

pair<int,int> mrg(pair<int,int> a,pair<int,int> b)
{
    set<int> k;
    k.insert(a.first);
    k.insert(a.second);
    k.insert(b.first);
    k.insert(b.second);
    auto it = k.end();
    it--;
    pair<int,int> res;
    res.first = *it;
    it--;
    res.second = *it;
    return res;
}

int getr(int i,int x)
{
    if(i == -1)
    {
        return 100;
    }
    return __builtin_popcount(x | tnum[i]);
}

pair<int,int> mrg2(pair<int,int> a,pair<int,int> b,int d)
{
    set<int> k;
    k.insert(a.first);
    k.insert(a.second);
    k.insert(b.first);
    k.insert(b.second);
    vector<int> ans;
    for(auto c:k)
        ans.push_back(c);
    sort(ans.begin(),ans.end(),[&](int x,int y){return getr(x,d) < getr(y,d);});
    pair<int,int> res = {ans[0],ans[1]};
    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    for(int i = 0;i < (1<<m);++i)
        dp[i] = {-1,-1};
    for(int i = 0;i < n;++i)
    {
        int num = 0;
        for(int j = 0;j < m;++j)
        {
            cin >> a[j][i];
            cou[j] += a[j][i];
            num += a[j][i] * (1<<j);
        }
     //   cout << num << ' ';
        dp[num] = mrg(dp[num],{i,-1});
        x[num] ++;
        tnum[i] = num;
    }
    for(int j = 0;j < m;++j)
    {
        for(int i = 0;i < (1<<m);++i)
        {
            if((i & (1<<j)) == 0)
            {
                dp[i ^ (1<<j)] = mrg(dp[i^(1<<j)],dp[i]);
            }
        }
    }
    for(int j = 0;j < (1<<m);++j)
    {
        mx[j] = dp[j];
    }
    for(int j = 0;j < m;++j)
    {
        for(int i = (1<<m)-1;i >= 0;--i)
        {
            if((i & (1<<j)))
            {
                mx[i ^ (1<<j)] = mrg2(mx[i^(1<<j)],mx[i],(i^(1<<j)));
            }
        }
    }
    for(int i = 0;i < n;++i)
    {
        int ans = 0;
        for(int j = 0;j < m;++j)
        {
            cou[j] -= a[j][i];
        }
        int mask = (1<<m)-1;
        for(int j = 0;j < m;++j)
        {
            if(cou[j] > n/2)
            {
                ans ++;
            }
            if(cou[j] == n/2)
            {
                mask ^= (1<<j);
            }
        }
        for(int j = 0;j < m;++j)
        {
            cou[j] += a[j][i];
        }
        pair<int,int> c = mx[mask];
        if(c.first == i)
        {
            ans += m-getr(c.second,mask);
        }
        else
            ans += m-getr(c.first,mask);
        cout << ans << "\n";
    }
}

• 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