Submission #793177

#	Time	Username	Problem	Language	Result	Execution time	Memory
793177		Cookie	Council (JOI23_council)	C++14	100 / 100	336 ms	49184 KiB

council

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("FEEDING.INP");
ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
using u128 = __uint128_t;
//const int x[4] = {1, -1, 0, 0};
//const int y[4] = {0, 0, 1, -1};
const ll mod = 1e9 + 7, inf = 1e9;
const int mxn = 1e5 + 5;
int n, m;
pii son[(1 << 20)];
char c[300005][21];
int cnt[(1 << 20)], val[20], mask[300005];
pair<pii, pii>dp[(1 << 20)];
bool ckmx(pii a, pii b){
    if(b.fi == 0)return(1);
    return(a.se > b.se);
}
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < m; j++){
            cin >> c[i][j];
            if(c[i][j] == '1'){
                mask[i] += (1 << j);
                val[j]++;
            }
        }
        mask[i] = (((1 << m) - 1) ^ mask[i]);
        if(!son[mask[i]].fi)son[mask[i]].fi = i;
        else if(!son[mask[i]].se)son[mask[i]].se = i;
    }
    for(int i = 0; i < (1 << m); i++){
        cnt[i] = __builtin_popcount(i);
    }
    for(int i = 0; i < m; i++){
        for(int j = 0; j < (1 << m); j++){
            if(!(j & (1 << i))){
                int &x = son[j].fi, &y = son[j].se, candx = son[j ^ (1 << i)].fi, candy = son[j ^ (1 << i)].se;
                if(x){
                    if(!y){
                        if(candx && candx != x)y = candx;
                        else if(candy && candy != x)y = candy;
                    }
                }else{
                    if(candx){
                        x = candx;
                        if(candy)y = candy;
                    }else{
                        if(candy)x = candy;
                    }
                }
                
            }
        }
    }
    for(int i = 0; i < (1 << m); i++){
        
        dp[i] = make_pair(make_pair(son[i].first, ((son[i].first ? cnt[i] : 0))), make_pair(son[i].second, (son[i].second ? cnt[i] : 0)));
        
    }
    
    for(int i = 0; i < m; i++){
        for(int j = 0; j < (1 << m); j++){
            if(j & (1 << i)){
                auto [cand1, cand2] = dp[j ^ (1 << i)];
                
                if(cand1.fi && ckmx(cand1, dp[j].se)){
                    pii rem = dp[j].se;
                    dp[j].se = cand1;
                    
                    if(ckmx(dp[j].se, dp[j].fi)){
                        
                        swap(dp[j].fi, dp[j].se);
                    }
                    if(dp[j].fi.fi == dp[j].se.fi){
                        dp[j].se = rem;
                    }
                }if(cand2.fi && ckmx(cand2, dp[j].se)){
                    pii rem = dp[j].se;
                    dp[j].se = cand2;
                    if(ckmx(dp[j].se, dp[j].fi)){
                        swap(dp[j].fi, dp[j].se);
                    }
                    if(dp[j].fi.fi == dp[j].se.fi){
                        dp[j].se = rem;
                    }
                }
            }
        }
    }
    
    for(int i = 1; i <= n; i++){
        int mask = 0, ans = 0;
        for(int j = 0; j < m; j++){
            if(c[i][j] == '1'){
                val[j]--; 
            }
            if(val[j] == n / 2){
                mask += (1 << j); ans++;
            }else if(val[j] > n / 2)ans++;
            if(c[i][j] == '1'){
                val[j]++;
            }
        }
        //cout << mask << " ";
        auto [res1, res2] = dp[mask];
        
        if(res1.fi != i){
            //cout << res1.se << " " << " " << cnt[mask] << " ";
            cout << ans - (cnt[mask] - res1.se) << "\n";
        }else{
            assert(res2.fi != i);
            cout << ans - (cnt[mask] - res2.se) << "\n";
        }
        
    }
    return(0);
}

Compilation message (stderr)

council.cpp: In function 'int main()':
council.cpp:82:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |                 auto [cand1, cand2] = dp[j ^ (1 << i)];
      |                      ^
council.cpp:123:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  123 |         auto [res1, res2] = dp[mask];
      |              ^

• 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