Submission #1033348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033348		Andrey	Council (JOI23_council)	C++14	100 / 100	543 ms	46980 KiB

council

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

vector<pair<int,int>> bruh((1 << 20),{-1,-1});
vector<pair<int,int>> dp((1 << 20),{-1,-1});
vector<pair<int,int>> idk((1 << 20),{0,0});
vector<pair<int,int>> pos((1 << 20),{-1,-1});

void merge(int x, int c, int d) {
    if(c == -1) {
        return;
    }
    if(pos[x].first == c) {
        idk[x] = {max(d,idk[x].first),idk[x].second};
    }
    else if(pos[x].second == c) {
        idk[x] = {idk[x].first,max(idk[x].second,d)};
        if(idk[x].first < idk[x].second) {
            idk[x] = {idk[x].second,idk[x].first};
            pos[x] = {pos[x].second,pos[x].first};
        }
    }
    else {
        if(d > idk[x].first) {
            idk[x] = {d,idk[x].first};
            pos[x] = {c,pos[x].first};
        }
        else if(d > idk[x].second) {
            idk[x] = {idk[x].first,d};
            pos[x] = {pos[x].first,c};
        }
    }
}

pair<int,int> calc(pair<int,int> a, int b) {
    if(b == -1) {
        return a;
    }
    if(a.first == -1) {
        return {b,-1};
    }
    else if(a.second == -1 && a.first != b) {
        return {a.first,b};
    }
    return a;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,m,a;
    cin >> n >> m;
    vector<int> br(m);
    vector<int> haha(n);
    for(int i = 0; i < n; i++) {
        int c = 0,d = m;
        for(int j = 0; j < m; j++) {
            cin >> a;
            br[j]+=a;
            d-=a;
            c+=a*(1 << j);
        }
        bruh[c] = calc(bruh[c],i);
        haha[i] = c;
    }
    for(int i = 0; i < (1 << m); i++) {
        dp[i] = bruh[i];
        for(int j = 0; j < m; j++) {
            if((1 << j)&i) {
                dp[i] = calc(dp[i],dp[i-(1 << j)].first);
                dp[i] = calc(dp[i],dp[i-(1 << j)].second);
            }
        }
    }
    for(int i = (1 << m)-1; i >= 0; i--) {
        int br = 0;
        for(int j = 0; j < m; j++) {
            if(((1 << j)&i) == 0) {
                br++;
            }
        }
        if(dp[i].first != -1) {
            merge(i,dp[i].first,br);
        }
        if(dp[i].second != -1) {
            merge(i,dp[i].second,br);
        }
        for(int j = 0; j < m; j++) {
            if(((1 << j)&i) == 0) {
                merge(i,pos[i+(1 << j)].first,idk[i+(1 << j)].first);
                merge(i,pos[i+(1 << j)].second,idk[i+(1 << j)].second);
            }
        }
    }
    for(int i = 0; i < n; i++) {
        int x = 0,ans = 0;
        for(int j = 0; j < m; j++) {
            int c = br[j];
            if((1 << j)&haha[i]) {
                c--;
            }
            if(c == n/2) {
                x+=(1 << j);
            }
            if(c > n/2) {
                ans++;
            }
        }
        x = (1 << m)-1-x;
        if(pos[x].first == i) {
            cout << ans+idk[x].second << "\n";
        }
        else {
            cout << ans+idk[x].first << "\n";
        }
    }
    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