Submission #884510

#	Time	Username	Problem	Language	Result	Execution time	Memory
884510		fanwen	Council (JOI23_council)	C++17	100 / 100	3332 ms	24912 KiB

council

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define file(name)                  \
    if(fopen(name".inp", "r"))      \
        freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \

const int MAX = 3e5 + 5;

int n, m, a[MAX], num[25], Min[1 << 10][1 << 10], cnt[1 << 10][1 << 10];
vector <int> adj[1 << 10];

void you_make_it(void) {
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < m; ++j) {
			int x; cin >> x;
			if(x) a[i] |= (1 << j);
			num[j] += x;
		}
		adj[a[i] & ((1 << m / 2)  - 1)].push_back(a[i] >> (m / 2));	
	}    

	for (int x = 0; x < (1 << m / 2); ++x) {
		for (auto y : adj[x]) cnt[x][y]++;
		for (int y = 0; y < (1 << (m - m / 2)); ++y) {
			Min[x][y] = m + 1;
			for (auto k : adj[x]) {
				Min[x][y] = min(Min[x][y], __builtin_popcount(y & k));
			} 
		}
	}

	for (int i = 1; i <= n; ++i) {
		int res = 0, ans = 0, fir = a[i] & ((1 << (m / 2)) - 1), sec = a[i] >> (m / 2);
		for (int j = 0; j < m; ++j) {
			int total = num[j] - (a[i] >> j & 1);
			if(total > n / 2) ans++;
			else if(total == n / 2) res |= (1 << j);
		}

		int val = m + 1;

		for (int mask = 0; mask < (1 << m / 2); ++mask) {
			if(mask != fir) {
				val = min(val, __builtin_popcount(mask & res) + Min[mask][res >> (m / 2)]);
			} else {
				for (int tmp = 0; tmp < (1 << (m - m / 2)); ++tmp) {
					if(cnt[mask][tmp] and (tmp != sec or cnt[mask][tmp] > 1)) {
						val = min(val, __builtin_popcount(mask & res) + __builtin_popcount(tmp & (res >> (m / 2))));
					}
				}
			}
		}
		cout << ans + __builtin_popcount(res) - val << '\n';
	}

}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    file("council");
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Compilation message (stderr)

council.cpp: In function 'int main()':
council.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
council.cpp:70:5: note: in expansion of macro 'file'
   70 |     file("council");
      |     ^~~~
council.cpp:10:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \
      |                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
council.cpp:70:5: note: in expansion of macro 'file'
   70 |     file("council");
      |     ^~~~

• 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