Submission #880567

#	Time	Username	Problem	Language	Result	Execution time	Memory
880567		sysia	Council (JOI23_council)	C++17	100 / 100	523 ms	48444 KiB

council

//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
const int oo = 1e18;

void solve(){
    int n, m; cin >> n >> m;
    vector<int>a(n+1), vote(m+1);
    for (int i = 1; i<=n; i++){
        for (int j = m-1; j>=0; j--){
            int k; cin >> k;
            if (k == 1){
                a[i] += (1<<j);
                vote[j]++;
            }
        }
    }
    vector<T>D1((1<<m), {oo, oo}), D2((1<<m), {oo, oo+1});
    auto f = [&](int a, int b, int w){
        T x = D1[b];
        T y = D2[b];
        x.first += w;
        y.first += w;
        if (D2[a] > x){
            swap(D2[a], x);
            if (D1[a].second == D2[a].second) swap(D2[a], x);
            if (D1[a] > D2[a]) swap(D1[a], D2[a]);  
        }
        if (D2[a] > y && D1[a].second != y.second) swap(D2[a], y);
    };
    debug(a);
    for (int i = 1; i<=n; i++){
        int x = (~a[i])&((1<<m)-1);
        // debug(x);
        if (D1[x].first == 0) D2[x] = {0, i};
        else D1[x] = {0, i};
    }
    
    for (int i = 0; i<m; i++){
        for (int mask = 0; mask<(1<<m); mask++){
            if (mask&(1<<i)){
                //zabranie bitu jest kosztem 0
                f(mask^(1<<i), mask, 0);
            }
        }
    }
    for (int i = 0; i<m; i++){
        for (int mask = 0; mask<(1<<m); mask++){
            if (mask&(1<<i)){
                //dodanie bitu kosztem 1
                f(mask, mask^(1<<i), 1);
            }
        }
    }
    debug(D1);
    debug(D2);
    for (int i = 1; i<=n; i++){
        int mask = 0, ans = 0;
        for (int j = 0; j<m; j++){
            int b = vote[j] - (a[i]&(1<<j) ? 1 : 0);
            if (b >= n/2) ans++;
            if (b < n/2) {}
            if (b == n/2) mask += (1<<j);
        }
        debug(i, mask, ans);
        if (D1[mask].second == i) ans -= D2[mask].first;
        else ans -= D1[mask].first;
        cout << ans << "\n";
    }
}

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

    solve();

    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