Submission #944537

#	Time	Username	Problem	Language	Result	Execution time	Memory
944537		nextgenxing	Council (JOI23_council)	C++14	100 / 100	1949 ms	39020 KiB

council

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define F0R(i, x) FOR(i, 0, x)
#define FORd(i, a, b) for(int i = (b)-1; i >= (a); i--)
#define F0Rd(i, x) FORd(i, 0, x)
const int MAX_N = 3e5+69;
const ll MOD = 1000000007;
const ll INF = 1e18;

int n, m, k;
int nums[MAX_N], tot[20];
pii val1[1 << 20];
pair<pii, pii> val2[1 << 20];

int main(int argc, const char * argv[]){
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    cin >> n >> m; k = n/2;
    F0R(i, n) F0R(j, m){
        int x; cin >> x;
        if(x) nums[i] ^= 1 << j;
        tot[j] += x;
    }
    F0R(i, n) nums[i] ^= (1 << m)-1;
    F0R(i, 1 << m) val1[i] = {-1, -1};
    F0R(i, n){
        if(~val1[nums[i]].ff) val1[nums[i]].ss = i;
        else val1[nums[i]].ff = i;
    }
    F0R(i, m) F0R(msk, 1 << m) if(msk&(1 << i)){
        vector<int> v;
        v.push_back(val1[msk].ff), v.push_back(val1[msk].ss);
        v.push_back(val1[msk^(1 << i)].ff), v.push_back(val1[msk^(1 << i)].ss);
        sort(all(v)), reverse(all(v));
        val1[msk^(1 << i)] = {v[0], v[1]};
    }
    F0R(msk, 1 << m){
        if(~val1[msk].ff)
            val2[msk].ff = {__builtin_popcount(msk), val1[msk].ff};
        else val2[msk].ff = {0, -1};
        if(~val1[msk].ss)
            val2[msk].ss = {__builtin_popcount(msk), val1[msk].ss};
        else val2[msk].ss = {0, -1};
    }
    F0R(i, m) F0R(msk, 1 << m) if(msk&(1 << i)){
        vector<pii> v;
        v.push_back(val2[msk].ff), v.push_back(val2[msk].ss);
        v.push_back(val2[msk^(1 << i)].ff), v.push_back(val2[msk^(1 << i)].ss);
        sort(all(v)), reverse(all(v));
        int k = 2;
        val2[msk] = {v[0], v[1]};
        while(val2[msk].ff.ss == val2[msk].ss.ss)
            val2[msk].ss = v[k++];
    }
    F0R(i, n){
        int val = 0, ans = 0;
        F0R(j, m){
            if(tot[j] > k+1) ans++;
            if(tot[j] == k+1){
                if(!(nums[i]&(1 << j))) val ^= (1 << j);
                else ans++;
            }
            if((nums[i]&(1 << j)) && tot[j] == k) val ^= (1 << j);
        }
        if(i == val2[val].ff.ss) cout << ans+val2[val].ss.ff << '\n';
        else cout << ans+val2[val].ff.ff << '\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