Submission #1162351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162351		brinton	Council (JOI23_council)	C++20	6 / 100	220 ms	22336 KiB

council

#include <bits/stdc++.h>
using namespace std;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    //start here
    int N,k;
    cin >> N >> k;
    vector<vector<int>> A(N,vector<int>(k));
    for(auto &i:A){
        for(auto &j:i)cin >> j;
    }
    // 0: < 絕，1: = 絕, 2: = 絕+1, 3: > 絕+1;
    vector<int> cnt(k,0);
    for(auto &v:A){
        for(int i = 0;i < k;i++){
            cnt[i] += v[i];
        }
    }
    vector<array<pair<int,int>,2>> dp((1 << k),{make_pair(0,-1),make_pair(0,-1)});//{{cnt1,loc1},{cnt2,loc2}};
    for(int loc = 0;loc < N;loc++){
        auto i = A[loc];
        // reverse
        int key = 0;
        for(auto &j:i){
            key*=2;
            key += j;
        }
        // cout << ((~key)&((1 << k)-1)) << endl;
        key = ((~key)&((1 << k)-1));

        dp[key][1] = max(dp[key][1],{__builtin_popcount(key),loc});
        if(dp[key][1] > dp[key][0])swap(dp[key][1],dp[key][0]);
    }
    // push lazy tag
    for(int mask = (1 << k)-1;mask >= 0;mask--){
        // push_down
        for(int i = 0;i < k;i++){
            if((mask|(1 << i)) == mask){
                // push_0
                int nxt = mask-(1 << i);
                auto [cnt1,loc1] = dp[mask][0];
                auto [cnt2,loc2] = dp[mask][1];

                if(dp[nxt][0].second != loc1) dp[nxt][1] = max(dp[nxt][1],{cnt1-1,loc1});
                if(dp[nxt][1] > dp[nxt][0])swap(dp[nxt][1],dp[nxt][0]);
                if(dp[nxt][0].second != loc2) dp[nxt][1] = max(dp[nxt][1],{cnt2-1,loc2});
                if(dp[nxt][1] > dp[nxt][0])swap(dp[nxt][1],dp[nxt][0]);
            }
        }
    }
    // bitmask dp
    for(auto i:dp){
        assert(i[0].second != i[1].second || i[0].second == -1);
    }
    for(int mask = 0;mask < (1 << k);mask++){
        // pull up
        for(int i = 0;i < k;i++){
            if((mask|(1 << i)) == mask){
                int prev = mask-(1 << i);

                if(dp[mask][0].second != dp[prev][0].second) dp[mask][1] = max(dp[mask][1],dp[prev][0]);
                if(dp[mask][1] > dp[mask][0]) swap(dp[mask][1],dp[mask][0]);
                if(dp[mask][0].second != dp[prev][1].second) dp[mask][1] = max(dp[mask][1],dp[prev][1]);
                if(dp[mask][1] > dp[mask][0]) swap(dp[mask][1],dp[mask][0]);
                // dp[mask] = max(dp[mask],dp[mask-(1 << i)]);
            }
        }
    }
    for(auto i:dp){
        assert(i[0].second != i[1].second || i[0].second == -1);
    }
    // for(int i = 0;i < (1 << k);i++){
    //     cout << i << ":" << dp[i] << endl;
    // }
    for(int loc = 0;loc < N;loc++){
        auto v = A[loc];
        // answer query
        int ans = 0;
        int mask = 0;
        for(int i = 0;i < k;i++){
            if(cnt[i] > N/2+1){
                // cout << "A";
                ans++;
                continue;
            }
            if(cnt[i] < N/2){
                // cout << "B";
                continue;
            }
            if(v[i] == 1){
                if(cnt[i] == N/2){
                    // cout << "C";
                    continue;
                }else{
                    // cout << "D";
                    mask |= (1 << (k-i-1));
                }
            }else{
                if(cnt[i] == N/2){
                    // cout << "E";
                    mask |= (1 << (k-i-1));
                }else{
                    // cout << "F";
                    ans++;
                    continue;
                }
            }
        }
        // cout << ans << " " << bitset<12>(mask) << endl;
        // cout << dp[mask][0].first << "," << dp[mask][0].second << " " ;
        // cout << dp[mask][1].first << "," << dp[mask][1].second << endl;
        if(dp[mask][0].second == loc){
            ans += dp[mask][1].first;
        }else{
            ans += dp[mask][0].first;
        }
        cout << ans << '\n';
    }
}
/*
dp[i] = {{cnt1,mask1},{cnt2,mask2}};
*/

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