Submission #1172717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172717		Zero_OP	Council (JOI23_council)	C++20	100 / 100	824 ms	30636 KiB

council

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r)-1; i >= (l); --i)

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sz(v) (int)v.size()

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

using ll = long long;
using db = double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;

using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<db>;
using vb = vector<bool>;
using vc = vector<char>;

using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;


void setIO(){
      ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
      freopen("task.inp", "r", stdin);
      freopen("task.out", "w", stdout);
#endif // LOCAL
}

const int MAX = 3e5 + 5;

int N, M, vote[20], mask_vote[MAX];

int count_bits(int x){
      return __builtin_popcount(x);
}

int main(){
      setIO();

      cin >> N >> M;
      FOR(i, 0, N){
            FOR(j, 0, M){
                  char c; cin >> c;
                  if(c == '1') {
                        mask_vote[i] |= (1 << j);
                        ++vote[j];
                  }
            }
      }

      int zero = 0, one = 0, target = (N/2);
      FOR(i, 0, M){
            if(vote[i] < target) continue;
            if(vote[i] == target) zero |= (1 << i);
            if(vote[i] == target+1) one |= (1 << i);
      }

      vpi dp(1 << M, mp(-1, -1));
      vi inv(N);
      FOR(i, 0, N){
            inv[i] = (((1 << M) - 1) ^ mask_vote[i]);
//            cout << bitset<12>(inv[i]) << "!!\n";
            if(dp[inv[i]].ff == -1) dp[inv[i]].ff = i;
            else if(dp[inv[i]].ss == -1) dp[inv[i]].ss = i;
      }

      FOR(i, 0, M){
            FOR(mask, 0, (1 << M)){
                  if(mask >> i & 1 ^ 1){
                        vi lst;
                        if(dp[mask].ff != -1) lst.pb(dp[mask].ff);
                        if(dp[mask].ss != -1) lst.pb(dp[mask].ss);
                        if(dp[mask ^ (1 << i)].ff != -1) lst.pb(dp[mask ^ (1 << i)].ff);
                        if(dp[mask ^ (1 << i)].ss != -1) lst.pb(dp[mask ^ (1 << i)].ss);
                        sort(all(lst));

                        if(sz(lst)>0) dp[mask].ff = lst[0];
                        if(sz(lst)>1) dp[mask].ss = lst[1];
                  }
            }
      }

      vector<pair<pi, pi>> F(1 << M, mp(mp(-1, -1), mp(-1, -1)));

      int T = 0;
      vi access(N), value(N);

      auto add = [&](int mask, const pi& v){
            if(F[mask].ff.ss == v.ss){
                  maximize(F[mask].ff, v);
                  if(F[mask].ff < F[mask].ss) swap(F[mask].ff, F[mask].ss);
                  return;
            }

            if(F[mask].ss.ss == v.ss){
                  maximize(F[mask].ss, v);
                  if(F[mask].ff < F[mask].ss) swap(F[mask].ff, F[mask].ss);
                  return;
            }

            maximize(F[mask].ss, v);
            if(F[mask].ff < F[mask].ss) swap(F[mask].ff, F[mask].ss);
      };

      FOR(mask, 0, (1 << M)){
            if(dp[mask].ff != -1) add(mask, mp(count_bits(mask), dp[mask].ff));
            if(dp[mask].ss != -1) add(mask, mp(count_bits(mask), dp[mask].ss));

//            cout << bitset<12>(mask) << " : (" << F[mask].ff.ss << ' ' << F[mask].ff.ss << ") (";
//            cout << F[mask].ss.ff << ' ' << F[mask].ss.ss << ")\n";
      }

      FOR(i, 0, M){
            FOR(mask, 0, (1 << M)){
                  if(mask >> i & 1){
                        if(F[mask ^ (1 << i)].ff.ff != -1) add(mask, F[mask ^ (1 << i)].ff);
                        if(F[mask ^ (1 << i)].ss.ff != -1) add(mask, F[mask ^ (1 << i)].ss);
                  }
            }
      }


      FOR(i, 0, N){
            int result = 0, q = 0;
            FOR(j, 0, M){
                  if(vote[j] - (mask_vote[i] >> j & 1) < target) continue;
                  if(vote[j] - (mask_vote[i] >> j & 1) == target) q |= (1 << j);
                  if(vote[j] - (mask_vote[i] >> j & 1) > target) ++result;
            }

//            cout << bitset<12>(q) << ' ' << result << '\n';
//
//            cout << F[q].ff.ff << ' ' << F[q].ff.ss << ' ' << F[q].ss.ff << ' ' << F[q].ss.ss << '\n';

            if(F[q].ff.ss != i) q = F[q].ff.ff;
            else q = F[q].ss.ff;

//            cout << "extra : " << q << '\n';

            cout << result + q << '\n';
      }

      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