oj.uz

Submission #757731

# Submission time Handle Problem Language Result Execution time Memory
757731 2023-06-13T16:39:34 Z happypotato Council (JOI23_council) C++17
25 / 100
 734 ms 58164 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
// global
int a[300001];
int n, m;
int dpf[(1 << 20)]; // 0: 0, -1: 2+, x: position x
pii dpb[(1 << 20)]; // {which level != 0, which level -1}
bool vis[(1 << 20)];
int ps[300001][20];
void init() {
	// init

}
void PrecompDPF() {
	for (int i = 1; i <= n; i++) {
		if (dpf[a[i]] == 0) dpf[a[i]] = i;
		else dpf[a[i]] = -1;
	}
	for (int bit = 0; bit < m; bit++) {
		for (int conf = 0; conf < (1 << m); conf++) {
			if (conf & (1 << bit)) {
				int prev = (conf ^ (1 << bit));
				// cerr << "ADD " << prev << " TO " << conf << endl;
				if (dpf[prev] == -1) {
					dpf[conf] = -1;
				} else if (dpf[prev] != 0) {
					if (dpf[conf] == 0) {
						dpf[conf] = dpf[prev];
					} else {
						dpf[conf] = -1;
					}
				}
			}
		}
	}
}
bool comp(int &lhs, int &rhs) {
	return __builtin_popcount(lhs) < __builtin_popcount(rhs);
}
void PrecompDPB() {
	for (int conf = 0; conf < (1 << m); conf++) {
		if (dpf[conf] == -1) {
			dpb[conf] = {conf, conf};
		} else if (dpf[conf] != 0) {
			dpb[conf] = {conf, -1};
		} else {
			dpb[conf] = {-1, -1};
		}
		vis[conf] = false;
		// cerr << conf << ' ' << dpb[conf].ff << ' ' << dpb[conf].ss << endl;
	}
	for (int bits = m - 1; bits >= 0; bits--) {
		for (int conf = 0; conf < (1 << m); conf++) {
			if (__builtin_popcount(conf) != bits) continue;
			int ncur;
			int cur = 0;
			for (int i = 0; i < m; i++) {
				if (!bool(conf & (1 << i))) {
					ncur = (conf ^ (1 << i));
					if (dpb[ncur].ff != -1) {
						if (comp(dpb[ncur].ff, dpb[conf].ff)) {
							dpb[conf].ff = dpb[ncur].ff;
						}
						if (dpf[dpb[ncur].ff] == -1) {
							if (comp(dpb[ncur].ff, dpb[conf].ss)) {
								dpb[conf].ss = dpb[ncur].ff;
							}
						} else if (cur == 0) {
							cur = dpb[ncur].ff;
						} else if (dpf[cur] != dpf[dpb[ncur].ff]) {
							// take larger one
							if (comp(cur, dpb[cur].ff)) {
								if (comp(dpb[ncur].ff, dpb[conf].ss)) {
									dpb[conf].ss = dpb[ncur].ff;
								}
							} else {
								if (comp(cur, dpb[conf].ss)) {
									dpb[conf].ss = cur;
								}
								cur = dpb[cur].ff;
							}
						}
					}
					if (dpb[ncur].ss != -1) {
						if (comp(dpb[ncur].ss, dpb[conf].ss)) {
							dpb[conf].ss = dpb[ncur].ss;
						}
						if (comp(dpb[ncur].ss, dpb[conf].ff)) {
							dpb[conf].ff = dpb[ncur].ss;
						}
					}
				}
			}
		}
	}
}
void PrecompPS() {
	for (int j = 0; j < m; j++) {
		ps[0][j] = 0;
		for (int i = 1; i <= n; i++) {
			ps[i][j] = ps[i - 1][j] + bool(a[i] & (1 << j));
		}
	}
}
void st7() {
	PrecompDPF();
	// cerr << "DPF:\n";
	// for (int i = 0; i < (1 << m); i++) cerr << dpf[i] << ' '; cerr << endl;
	// cerr << "END\n";
	PrecompDPB();
	// cerr << "DPB:\n";
	// for (int i = 0; i < (1 << m); i++) {
	// 	cerr << i << ": " << dpb[i].ff << ' ' << dpb[i].ss << endl;
	// }
	// cerr << "END\n";
	PrecompPS();
	for (int i = 1; i <= n; i++) {
		int ans = 0, tar = 0;
		for (int j = 0; j < m; j++) {
			if ((ps[n][j] - bool(a[i] & (1 << j))) > (n >> 1)) {
				ans++;
			} else if ((ps[n][j] - bool(a[i] & (1 << j))) == (n >> 1)) {
				tar |= (1 << j);
			}
		}
		tar ^= ((1 << m) - 1);
		// cerr << ans << ' ' << tar << endl;
		// cerr << dpb[tar].ff << ' ' << dpb[tar].ss << endl;
		int buff = 0;
		if (dpb[tar].ff != -1) {
			if (dpf[dpb[tar].ff] != i) {
				buff = max(buff, m - __builtin_popcount(dpb[tar].ff));
			}
		}
		if (dpb[tar].ss != -1) {
			buff = max(buff, m - __builtin_popcount(dpb[tar].ss));
		}
		// cerr << ans << ' ' << buff << endl;
		ans += buff;
		cout << ans << endl;
	}
}
void st6() {
	return st7();
}
void st5() {
	return st7();
}
void st4() {
	return st7();
}
void st3() {
	return st7();
}
void st2() {
	return st7();
	PrecompPS();
	for (int i = 1; i <= n; i++) {
		int ans = 0;
		int cur;
		for (int j = 1; j <= n; j++) {
			if (i == j) continue;
			cur = 0;
			for (int k = 0; k < m; k++) {
				cur += ((ps[n][k] - bool(a[i] & (1 << k)) - bool(a[j] & (1 << k))) >= (n >> 1));
			}
			ans = max(ans, cur);
		}
		cout << ans << endl;
	}
}
void st1() {
	return st2();
}
void solve() {
	// solve
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		a[i] = 0;
		bool temp;
		for (int j = 0; j < m; j++) {
			cin >> temp;
			if (temp) {
				a[i] |= (1 << j);
			}
		}
	}
	if (n <= 300) return st1();
	if (n <= 3000) return st2();
	if (m <= 2) return st3();
	if (m <= 10) return st4();
	if (m <= 14) return st5();
	if (m <= 17) return st6();
	return st7();
}
int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	init(); solve();
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 354 ms 21876 KB Output is correct
6 Correct 322 ms 17756 KB Output is correct
7 Correct 359 ms 20524 KB Output is correct
8 Correct 425 ms 20912 KB Output is correct
9 Correct 418 ms 25560 KB Output is correct
10 Incorrect 367 ms 19872 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 354 ms 21876 KB Output is correct
6 Correct 322 ms 17756 KB Output is correct
7 Correct 359 ms 20524 KB Output is correct
8 Correct 425 ms 20912 KB Output is correct
9 Correct 418 ms 25560 KB Output is correct
10 Incorrect 367 ms 19872 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 418 ms 51248 KB Output is correct
3 Correct 420 ms 51240 KB Output is correct
4 Correct 400 ms 50672 KB Output is correct
5 Correct 405 ms 51276 KB Output is correct
6 Correct 386 ms 50820 KB Output is correct
7 Correct 446 ms 51204 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 280 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 324 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 328 KB Output is correct
17 Correct 5 ms 852 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 418 ms 51248 KB Output is correct
3 Correct 420 ms 51240 KB Output is correct
4 Correct 400 ms 50672 KB Output is correct
5 Correct 405 ms 51276 KB Output is correct
6 Correct 386 ms 50820 KB Output is correct
7 Correct 446 ms 51204 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 280 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 324 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 328 KB Output is correct
17 Correct 5 ms 852 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 656 ms 55244 KB Output is correct
21 Correct 630 ms 54364 KB Output is correct
22 Correct 595 ms 54540 KB Output is correct
23 Correct 734 ms 55424 KB Output is correct
24 Correct 622 ms 55216 KB Output is correct
25 Correct 637 ms 55268 KB Output is correct
26 Correct 654 ms 55236 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 328 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 0 ms 340 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 1 ms 340 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 0 ms 340 KB Output is correct
43 Correct 1 ms 340 KB Output is correct
44 Correct 1 ms 340 KB Output is correct
45 Correct 1 ms 340 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 418 ms 51248 KB Output is correct
3 Correct 420 ms 51240 KB Output is correct
4 Correct 400 ms 50672 KB Output is correct
5 Correct 405 ms 51276 KB Output is correct
6 Correct 386 ms 50820 KB Output is correct
7 Correct 446 ms 51204 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 280 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 324 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 328 KB Output is correct
17 Correct 5 ms 852 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 656 ms 55244 KB Output is correct
21 Correct 630 ms 54364 KB Output is correct
22 Correct 595 ms 54540 KB Output is correct
23 Correct 734 ms 55424 KB Output is correct
24 Correct 622 ms 55216 KB Output is correct
25 Correct 637 ms 55268 KB Output is correct
26 Correct 654 ms 55236 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 328 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 0 ms 340 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 1 ms 340 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 0 ms 340 KB Output is correct
43 Correct 1 ms 340 KB Output is correct
44 Correct 1 ms 340 KB Output is correct
45 Correct 1 ms 340 KB Output is correct
46 Correct 2 ms 340 KB Output is correct
47 Correct 689 ms 57664 KB Output is correct
48 Correct 683 ms 56924 KB Output is correct
49 Correct 649 ms 57224 KB Output is correct
50 Correct 687 ms 57396 KB Output is correct
51 Correct 663 ms 57664 KB Output is correct
52 Correct 706 ms 57620 KB Output is correct
53 Correct 729 ms 58164 KB Output is correct
54 Correct 4 ms 596 KB Output is correct
55 Correct 5 ms 584 KB Output is correct
56 Correct 5 ms 712 KB Output is correct
57 Incorrect 5 ms 724 KB Output isn't correct
58 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 418 ms 51248 KB Output is correct
3 Correct 420 ms 51240 KB Output is correct
4 Correct 400 ms 50672 KB Output is correct
5 Correct 405 ms 51276 KB Output is correct
6 Correct 386 ms 50820 KB Output is correct
7 Correct 446 ms 51204 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 280 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 324 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 328 KB Output is correct
17 Correct 5 ms 852 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 656 ms 55244 KB Output is correct
21 Correct 630 ms 54364 KB Output is correct
22 Correct 595 ms 54540 KB Output is correct
23 Correct 734 ms 55424 KB Output is correct
24 Correct 622 ms 55216 KB Output is correct
25 Correct 637 ms 55268 KB Output is correct
26 Correct 654 ms 55236 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 328 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 0 ms 340 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 1 ms 340 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 0 ms 340 KB Output is correct
43 Correct 1 ms 340 KB Output is correct
44 Correct 1 ms 340 KB Output is correct
45 Correct 1 ms 340 KB Output is correct
46 Correct 2 ms 340 KB Output is correct
47 Correct 689 ms 57664 KB Output is correct
48 Correct 683 ms 56924 KB Output is correct
49 Correct 649 ms 57224 KB Output is correct
50 Correct 687 ms 57396 KB Output is correct
51 Correct 663 ms 57664 KB Output is correct
52 Correct 706 ms 57620 KB Output is correct
53 Correct 729 ms 58164 KB Output is correct
54 Correct 4 ms 596 KB Output is correct
55 Correct 5 ms 584 KB Output is correct
56 Correct 5 ms 712 KB Output is correct
57 Incorrect 5 ms 724 KB Output isn't correct
58 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 354 ms 21876 KB Output is correct
6 Correct 322 ms 17756 KB Output is correct
7 Correct 359 ms 20524 KB Output is correct
8 Correct 425 ms 20912 KB Output is correct
9 Correct 418 ms 25560 KB Output is correct
10 Incorrect 367 ms 19872 KB Output isn't correct
11 Halted 0 ms 0 KB -