Submission #776261

#	Time	Username	Problem	Language	Result	Execution time	Memory
776261		hugo_pm	Council (JOI23_council)	C++17	100 / 100	2877 ms	668532 KiB

council

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

#define all(v) (v).begin(), (v).end()
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define sz(v) ((int)((v).size()))

template<typename T>
void chmax(T &x, const T &v) { if (x < v) x = v; }
template<typename T>
void chmin(T &x, const T &v) { if (x > v) x = v; }

using pii = pair<int, int>;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
	bool first = true;
	string res = "[";
	for (const auto &x : v) {
		if (!first)
			res += ", ";
		first = false;
		res += to_string(x);
	}
	res += "]";
	return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
	cout << ' ' << to_string(H);
	dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

    int nbPerson, nbProp;
    cin >> nbPerson >> nbProp;
    vector<vector<int>> vote(nbPerson, vector<int>(nbProp));
    vector<int> somme(nbProp, 0);
    rep(iPerson, 0, nbPerson) {
        rep(iProp, 0, nbProp) {
            int x; cin >> x;
            vote[iPerson][iProp] = x;
            somme[iProp] += x;
        }
    }
    int seuil = nbPerson/2;
    int alwaysOk = 0;
    vector<int> useful, mask(nbPerson);
    rep(iProp, 0, nbProp) {
        if (seuil == somme[iProp] || somme[iProp] == seuil+1) {
            useful.push_back(iProp);
            rep(iPerson, 0, nbPerson) {
                if (vote[iPerson][iProp] == 0) {
                    mask[iPerson] += 1<<iProp;
                }
            }
        } else if (somme[iProp] >= seuil+2) {
            alwaysOk++;
        }
    }

    vector<vector<pii>> dp(1 << nbProp, {{-1, -1}, {-1, -1}});
    rep(iPerson, 0, nbPerson) {
        int x = mask[iPerson];
        dp[x].emplace_back(__builtin_popcountll(x), iPerson);
    }
    for (int x = (1<<nbProp)-1; x >= 0; --x) {
        //dbg(x, dp[x]);
        rep(bit, 0, nbProp) {
            int plusHaut = x | (1<<bit);
            if (plusHaut == x) continue;
            for (auto [pop, from] : dp[plusHaut]) if (pop > 0) {
                    dp[x].emplace_back(__builtin_popcount(x), from);
            }
        }
        sort(dp[x].rbegin(), dp[x].rend());
        dp[x].resize(unique(all(dp[x])) - dp[x].begin());
        dp[x].resize(2);
    }
    rep(x, 0, 1<<nbProp) {
        rep(bit, 0, nbProp) if (x & (1<<bit)){
            for (auto p: dp[x^(1<<bit)]) dp[x].push_back(p);
        }
        sort(dp[x].rbegin(), dp[x].rend());
        vector<pii> ps;
        rep(i, 0, sz(dp[x])) {
            if (i == 0 || dp[x][i].second != dp[x][i-1].second) {
                ps.push_back(dp[x][i]);
            }
        }
        dp[x] = ps;
        dp[x].resize(2);
    }
    rep(iChef, 0, nbPerson) {
        int M = 0;
        int middle = 0;
        for (int iProp : useful) {
            bool c1 = (vote[iChef][iProp] == 0 && somme[iProp] == seuil);
            bool c2 = (vote[iChef][iProp] == 1 && somme[iProp] == seuil+1);
            if (c1 || c2) {
                M += (1<<iProp);
            } else if (vote[iChef][iProp] == 0) {
                assert(somme[iProp] == seuil+1);
                ++middle;
            }
        }
        string s = bitset<12>(M).to_string();
        auto take = dp[M][0];
        //dbg(iChef, take.first, take.second, middle, alwaysOk);
        if (take.second == iChef) { take = dp[M][1]; }
        //dbg(iChef, take.first, take.second, middle, alwaysOk);
        cout << take.first + middle + alwaysOk << "\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