Submission #1308365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308365		thnhann	Council (JOI23_council)	C++20	25 / 100	4091 ms	24868 KiB

council

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma,lzcnt,popcnt")
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define ill pair<ll,ll>
#define el cout<<'\n'
#define int long long

const ll mod=1e9+7;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
const int nmax=1e6;
const int inf =2e9;

void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

using namespace std;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r)
{
    return uniform_int_distribution<int>(l, r) (rd);
}

//int n;
int cnt[25];
bool a[300005][20];
int n,m;
vector<int>p;
int maskfull;
int candidate[300005];
int ans = 0;

struct MIANDMI{
    int mi1;
    int idx;
    int mi2;
} mi[nmax + 5];

int type[25];
int id[25];
signed main()
{
   ios::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);



   cin >> n >> m;
   for(int i=1;i<=n;i++)
   {
       for(int j=1;j<=m;j++)
       {
           cin >> a[i][j];
           if(a[i][j])
                cnt[j]++;
       }
   }

   int k = n / 2;
   maskfull = 1;
   int timer = 0;

   for(int i=1;i<=m;i++)
   {
       if(cnt[i] >= k + 2)
       {
           ans++;
       }
       else
       {
           if(cnt[i] == k)
           {
            type[i] = 1;
            p.pb(i);
            id[i] = timer++;
           }
           else
            if(cnt[i] == k + 1)
           {
               type[i] = 2;
               p.pb(i);
               id[i] = timer++;
           }

       }
   }
//
//   for(auto i:p)
//    cout << i << " ";
//   el;

   for(int mask=0;mask<(1<<((int)p.size()));mask++)
   {
       mi[mask].mi1 = inf;
       mi[mask].mi2 = inf;
       for(int i=1;i<=n;i++)
       {
           int cur = 0;
           for(int j=0;j<p.size();j++)
            if((mask >> j) & 1)
           {
               if(a[i][p[j]])
                cur++;
           }
           if(mi[mask].mi1 > cur)
           {
               mi[mask].mi2 = mi[mask].mi1;
               mi[mask].mi1 = cur;
               mi[mask].idx = i;
           }
           else
           {
               if(mi[mask].mi2 > cur)
                mi[mask].mi2 = cur;
           }
       }
//       for(int j=0;j<p.size();j++)
//       {
//           if((mask >> j) & 1)
//            cout << p[j] << " ";
//       }
//       el;
//       cout << mi[mask].mi1 << " " << mi[mask].idx << " " << mi[mask].mi2;el;
   }

   for(int i=1;i<=n;i++)
   {
    int anscur = ans;
    vector<int>bucket;
    for(auto j:p)
    {
        if(a[i][j])
        {
            if(type[j] == 2)
            {
                bucket.pb(id[j]);
            }
        }
        else
        {
            if(type[j] == 1)
            {
                bucket.pb(id[j]);
            }
            else
                anscur++;
        }
    }
//    el;
//    cout << i;el;
//    for(auto bit:bucket)
//        cout << bit << " ";
//    el;
//    cout << anscur;el;
    int mask = 0;
    for(auto bit:bucket)
        mask |= (1<<bit);
    anscur += bucket.size();
    int div;
    if(i == mi[mask].idx)
        div = mi[mask].mi2;
    else
        div = mi[mask].mi1;
    anscur -= div;
    cout << anscur;el;

   }



}
//  "Can i get a kiss? And can u make it last forever?"

• Subtask 1: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 6 / 6
• Subtask 4: 19 / 19
• Subtask 5: 0 / 15
• Subtask 6: 0 / 22
• Subtask 7: 0 / 22