Submission #993193

#	Time	Username	Problem	Language	Result	Execution time	Memory
993193		onbert	Council (JOI23_council)	C++17	100 / 100	2001 ms	101208 KiB

council

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
bool cmp (int a, int b) {
    int A = 0, B = 0;
    for (int i=0;i<20;i++) if (a & (1<<i)) A++;
    for (int i=0;i<20;i++) if (b & (1<<i)) B++;
    return A < B;
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m;
    cin >> n >> m;
    int N = (1<<m);
    pair<int,int> mn[N][2];
    int sum[m], a[n+1][m];
    for (int i=0;i<m;i++) sum[i] = 0;
    for (int i=0;i<N;i++) {
        mn[i][0] = {-1, 0}, mn[i][1] = {-1, 0};
        for (int j=0;j<m;j++) if (i & (1<<j)) mn[i][0].second++, mn[i][1].second++;
    }
    for (int i=1;i<=n;i++) {
        int cur = 0;
        for (int j=0;j<m;j++) {
            cin >> a[i][j];
            cur += (!a[i][j]) * (1<<j);
            sum[j] += a[i][j];
        }
        if (mn[cur][0].first==-1) mn[cur][0] = {i, 0};
        else if (mn[cur][1].first==-1) mn[cur][1] = {i, 0};
    }

    vector<int> order(N);
    for (int i=0;i<N;i++) {
        order[i] = i;
    }
    sort(order.rbegin(), order.rend(), cmp);
    for (int u:order) {
        for (int i=0;i<m;i++) if (!(u & (1<<i))) {
            int v = (u | (1<<i));
            int id = mn[v][0].first;
            if (id!=-1 && id!=mn[u][0].first && id!=mn[u][1].first) {
                if (mn[u][0].first==-1) mn[u][0] = {mn[v][0].first, 0};
                else if (mn[u][1].first==-1) mn[u][1] = {mn[v][0].first, 0};
            }
            id = mn[v][1].first;
            if (id!=-1 && id!=mn[u][0].first && id!=mn[u][1].first) {
                if (mn[u][0].first==-1) mn[u][0] = {mn[v][1].first, 0};
                else if (mn[u][1].first==-1) mn[u][1] = {mn[v][1].first, 0};
            }
        }
    }
    // for (int i=0;i<N;i++) if (mn[i][0].second==0) {
    //     cout << mn[i][0].first << endl;
    //     for (int j=0;j<m;j++) cout << (bool)(i & (1<<j)); cout << endl;
    // }
    reverse(order.begin(), order.end());
    for (int u:order) {
        vector<pair<int,int>> vec;
        for (int i=0;i<m;i++) if (u & (1<<i)) {
            int v = u - (1<<i);
            // if (u==1473) {
            //     for (int j=0;j<m;j++) cout << (bool)(v & (1<<j)); cout << endl;
            // }
            for (auto [id, val]:mn[v]) if (id!=-1) vec.push_back({val+1, id});
        }
        sort(vec.begin(), vec.end());
        for (auto [val, id]:vec) {
            // if (u==1473) cout << id << " " << val << endl;
            if (id!=-1 && id!=mn[u][0].first && id!=mn[u][1].first) {
                if (mn[u][0].first==-1) mn[u][0] = {id, val};
                else if (mn[u][1].first==-1) mn[u][1] = {id, val};
            }
        }
    }

    int lim = n/2;
    for (int i=1;i<=n;i++) {
        int ans = 0, u = 0;
        for (int j=0;j<m;j++) {
            int cur = sum[j]-a[i][j];
            if (cur >= lim) ans++;
            if (cur==lim) u += (1<<j);
        }
        if (mn[u][0].first!=i) ans -= mn[u][0].second;
        else ans -= mn[u][1].second;
        // for (int j=0;j<m;j++) cout << (bool)(u & (1<<j)); cout << endl;
        // cout << mn[u][0].first << " " << mn[u][0].second << endl;
        // cout << mn[u][1].first << " " << mn[u][1].second << endl;
        cout << ans << "\n";
    }
}

• 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