Submission #987237

#	Time	Username	Problem	Language	Result	Execution time	Memory
987237		VinhLuu	Council (JOI23_council)	C++17	100 / 100	609 ms	31812 KiB

council

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
//#define int long long
//#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()
using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 3e5 + 5;
const int oo = 1e9 + 1;
const int mod = 1e9 + 7;
//const ll oo = 5e18;

int n, m, mask, cnt[22], a[N], b[N];
int dp[(1 << 20)][2][2];

// 0 0 -> val
// 0 1 -> idx
// -> first
// 1 0 -> val
// 1 1 -> idx
// -> second

void update(int u,pii x) {
    if(dp[u][0][0] < x.fi) {
        if(dp[u][0][1] != x.se) dp[u][1][0] = dp[u][0][0], dp[u][1][1] = dp[u][0][1];
        dp[u][0][0] = x.fi, dp[u][0][1] = x.se;
    }else if(dp[u][1][0] < x.fi && dp[u][0][1] != x.se) dp[u][1][0] = x.fi, dp[u][1][1] = x.se;
}


signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    #define task "v"
    if(fopen(task ".inp","r")){
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }

    cin >> n >> m;
    int full = (1 << m) - 1;
    for(int msk = 0; msk <= full; msk ++){
        dp[msk][0][0] = dp[msk][1][0] = 0;
        dp[msk][0][1] = dp[msk][1][1] = -1;
    }
    for(int i = 0; i < n; i ++){
        for(int j = 0; j < m; j ++){
            int x; cin >> x;
            cnt[j] += x;
            a[i] += x * (1 << j);
        }
        int u = __builtin_popcount(full ^ a[i]);
        update(full ^ a[i], {u, i});
    }

    for(int msk = full; msk >= 1; msk --){
        for(int j = 0; j < m; j ++){
            if((msk >> j) & 1){
                update(msk ^ (1 << j), {dp[msk][0][0] - 1, dp[msk][0][1]});
                update(msk ^ (1 << j), {dp[msk][1][0] - 1, dp[msk][1][1]});
            }
        }
    }


    for(int msk = 1; msk <= full; msk ++){
        for(int j = 0; j < m; j ++){
            if(!((msk >> j) & 1)){
                update(msk | (1 << j), {dp[msk][0][0], dp[msk][0][1]});
                update(msk | (1 << j), {dp[msk][1][0], dp[msk][1][1]});
            }
        }
    }

    for(int i = 0; i < n; i ++){
        int ans = 0;
        for(int j = 0; j < m; j ++){
            int tmp = cnt[j] - ((a[i] >> j) & 1);
            ans += (tmp > n / 2);
            b[i] += (1 << j) * (tmp == n / 2);
        }
        if (dp[b[i]][0][1] != i) ans += dp[b[i]][0][0];
        else ans += dp[b[i]][1][0];
        cout << ans << '\n';
    }
}

Compilation message (stderr)

council.cpp: In function 'int main()':
council.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen(task ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
council.cpp:43:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         freopen(task ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• 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