oj.uz

Submission #741874

# Submission time Handle Problem Language Result Execution time Memory
741874 2023-05-15T03:11:01 Z pavement Council (JOI23_council) C++17
40 / 100
 4000 ms 69036 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
//~ #define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define g4(a) get<4>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
using iiiii = tuple<int, int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, M, X[300005], cnt[25];
bool b;
basic_string<ii> vec[(1 << 20) + 5], ans[(1 << 20) + 5];

void merge(basic_string<ii> &a, basic_string<ii> &b) {
	basic_string<ii> tmp, tmp2;
	for (auto el : a) tmp.pb(mp(el.second, el.first));
	for (auto el : b) tmp.pb(mp(el.second, el.first));
	sort(tmp.begin(), tmp.end());
	for (int i = 0; i < (int)tmp.size(); i++) {
		if (i == 0 || tmp[i - 1].first != tmp[i].first) tmp2.pb(mp(tmp[i].second, tmp[i].first));
	}
	sort(tmp2.begin(), tmp2.end());
	while (tmp2.size() > 2) tmp2.ppb();
	a.clear();
	for (auto el : tmp2) a.pb(el);
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> b;
			X[i] |= (1 << j) * b;
			cnt[j] += b;
		}
		if ((int)vec[X[i]].size() < 2) vec[X[i]].pb(mp(__builtin_popcount(X[i]), i));
	}
	for (int m = 0; m < (1 << M); m++) {
		for (int s = m; ; s = (s - 1) & m) {
			merge(vec[s], vec[m]);
			if (s == 0) break;
		}
	}
	for (int m = 0; m < (1 << M); m++) {
		for (int s = m; ; s = (s - 1) & m) {
			// bm = s, k = m
			basic_string<ii> cpy;
			for (auto el : vec[s ^ m]) cpy.pb(mp(el.first + __builtin_popcount(s) - __builtin_popcount(m), el.second));
			merge(ans[s], cpy);
			if (s == 0) break;
		}
	}
	//~ for (int i = 0; i < (1 << M); i++) {
		//~ cout << "@ " << i << '\n';
		//~ for (auto el : ans[i]) cout << el.first << ' ' << el.second << '\n';
	//~ }
	for (int i = 1; i <= N; i++) {
		int cur = 0, bm = 0;
		for (int j = 0; j < M; j++) {
			if (X[i] & (1 << j)) cnt[j]--;
		}
		for (int j = 0; j < M; j++) {
			if (cnt[j] > N / 2) cur++;
			else if (cnt[j] == N / 2) cur++, bm |= (1 << j);
		}
		//~ cout << "BM: " << bm << '\n';
		for (auto el : ans[bm]) {
			//~ cout << el.first << ' ' << el.second << '\n';
			if (el.second != i) {
				cur -= el.first;
				break;
			}
		}
		cout << cur << '\n';
		for (int j = 0; j < M; j++) {
			if (X[i] & (1 << j)) cnt[j]++;
		}
	}
}

Compilation message

council.cpp:46:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   46 | main() {
      | ^~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 65876 KB Output is correct
2 Correct 124 ms 66104 KB Output is correct
3 Correct 33 ms 65880 KB Output is correct
4 Correct 33 ms 65936 KB Output is correct
5 Execution timed out 4094 ms 65868 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 65876 KB Output is correct
2 Correct 124 ms 66104 KB Output is correct
3 Correct 33 ms 65880 KB Output is correct
4 Correct 33 ms 65936 KB Output is correct
5 Execution timed out 4094 ms 65868 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 65888 KB Output is correct
2 Correct 92 ms 67680 KB Output is correct
3 Correct 93 ms 67724 KB Output is correct
4 Correct 78 ms 67660 KB Output is correct
5 Correct 103 ms 67712 KB Output is correct
6 Correct 82 ms 67788 KB Output is correct
7 Correct 102 ms 67688 KB Output is correct
8 Correct 33 ms 65924 KB Output is correct
9 Correct 32 ms 65864 KB Output is correct
10 Correct 33 ms 65936 KB Output is correct
11 Correct 34 ms 65876 KB Output is correct
12 Correct 33 ms 65868 KB Output is correct
13 Correct 33 ms 65936 KB Output is correct
14 Correct 38 ms 65976 KB Output is correct
15 Correct 38 ms 65904 KB Output is correct
16 Correct 41 ms 65960 KB Output is correct
17 Correct 33 ms 65960 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 65888 KB Output is correct
2 Correct 92 ms 67680 KB Output is correct
3 Correct 93 ms 67724 KB Output is correct
4 Correct 78 ms 67660 KB Output is correct
5 Correct 103 ms 67712 KB Output is correct
6 Correct 82 ms 67788 KB Output is correct
7 Correct 102 ms 67688 KB Output is correct
8 Correct 33 ms 65924 KB Output is correct
9 Correct 32 ms 65864 KB Output is correct
10 Correct 33 ms 65936 KB Output is correct
11 Correct 34 ms 65876 KB Output is correct
12 Correct 33 ms 65868 KB Output is correct
13 Correct 33 ms 65936 KB Output is correct
14 Correct 38 ms 65976 KB Output is correct
15 Correct 38 ms 65904 KB Output is correct
16 Correct 41 ms 65960 KB Output is correct
17 Correct 33 ms 65960 KB Output is correct
18 Correct 34 ms 65976 KB Output is correct
19 Correct 40 ms 65936 KB Output is correct
20 Correct 354 ms 67804 KB Output is correct
21 Correct 277 ms 67764 KB Output is correct
22 Correct 290 ms 67764 KB Output is correct
23 Correct 245 ms 68100 KB Output is correct
24 Correct 291 ms 67704 KB Output is correct
25 Correct 350 ms 67804 KB Output is correct
26 Correct 351 ms 67916 KB Output is correct
27 Correct 47 ms 66028 KB Output is correct
28 Correct 31 ms 65952 KB Output is correct
29 Correct 31 ms 65888 KB Output is correct
30 Correct 31 ms 65984 KB Output is correct
31 Correct 34 ms 65912 KB Output is correct
32 Correct 36 ms 65864 KB Output is correct
33 Correct 35 ms 65984 KB Output is correct
34 Correct 37 ms 65896 KB Output is correct
35 Correct 49 ms 66132 KB Output is correct
36 Correct 56 ms 65944 KB Output is correct
37 Correct 33 ms 65980 KB Output is correct
38 Correct 34 ms 65868 KB Output is correct
39 Correct 33 ms 65876 KB Output is correct
40 Correct 32 ms 65884 KB Output is correct
41 Correct 33 ms 65992 KB Output is correct
42 Correct 34 ms 65908 KB Output is correct
43 Correct 37 ms 65936 KB Output is correct
44 Correct 52 ms 65980 KB Output is correct
45 Correct 63 ms 66008 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 65888 KB Output is correct
2 Correct 92 ms 67680 KB Output is correct
3 Correct 93 ms 67724 KB Output is correct
4 Correct 78 ms 67660 KB Output is correct
5 Correct 103 ms 67712 KB Output is correct
6 Correct 82 ms 67788 KB Output is correct
7 Correct 102 ms 67688 KB Output is correct
8 Correct 33 ms 65924 KB Output is correct
9 Correct 32 ms 65864 KB Output is correct
10 Correct 33 ms 65936 KB Output is correct
11 Correct 34 ms 65876 KB Output is correct
12 Correct 33 ms 65868 KB Output is correct
13 Correct 33 ms 65936 KB Output is correct
14 Correct 38 ms 65976 KB Output is correct
15 Correct 38 ms 65904 KB Output is correct
16 Correct 41 ms 65960 KB Output is correct
17 Correct 33 ms 65960 KB Output is correct
18 Correct 34 ms 65976 KB Output is correct
19 Correct 40 ms 65936 KB Output is correct
20 Correct 354 ms 67804 KB Output is correct
21 Correct 277 ms 67764 KB Output is correct
22 Correct 290 ms 67764 KB Output is correct
23 Correct 245 ms 68100 KB Output is correct
24 Correct 291 ms 67704 KB Output is correct
25 Correct 350 ms 67804 KB Output is correct
26 Correct 351 ms 67916 KB Output is correct
27 Correct 47 ms 66028 KB Output is correct
28 Correct 31 ms 65952 KB Output is correct
29 Correct 31 ms 65888 KB Output is correct
30 Correct 31 ms 65984 KB Output is correct
31 Correct 34 ms 65912 KB Output is correct
32 Correct 36 ms 65864 KB Output is correct
33 Correct 35 ms 65984 KB Output is correct
34 Correct 37 ms 65896 KB Output is correct
35 Correct 49 ms 66132 KB Output is correct
36 Correct 56 ms 65944 KB Output is correct
37 Correct 33 ms 65980 KB Output is correct
38 Correct 34 ms 65868 KB Output is correct
39 Correct 33 ms 65876 KB Output is correct
40 Correct 32 ms 65884 KB Output is correct
41 Correct 33 ms 65992 KB Output is correct
42 Correct 34 ms 65908 KB Output is correct
43 Correct 37 ms 65936 KB Output is correct
44 Correct 52 ms 65980 KB Output is correct
45 Correct 63 ms 66008 KB Output is correct
46 Correct 119 ms 66012 KB Output is correct
47 Correct 1872 ms 68544 KB Output is correct
48 Correct 904 ms 68116 KB Output is correct
49 Correct 865 ms 68188 KB Output is correct
50 Correct 1174 ms 69012 KB Output is correct
51 Correct 797 ms 68172 KB Output is correct
52 Correct 2181 ms 68812 KB Output is correct
53 Correct 2164 ms 69032 KB Output is correct
54 Correct 1055 ms 66736 KB Output is correct
55 Correct 749 ms 66832 KB Output is correct
56 Correct 933 ms 66492 KB Output is correct
57 Correct 703 ms 66476 KB Output is correct
58 Correct 1046 ms 66544 KB Output is correct

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 65888 KB Output is correct
2 Correct 92 ms 67680 KB Output is correct
3 Correct 93 ms 67724 KB Output is correct
4 Correct 78 ms 67660 KB Output is correct
5 Correct 103 ms 67712 KB Output is correct
6 Correct 82 ms 67788 KB Output is correct
7 Correct 102 ms 67688 KB Output is correct
8 Correct 33 ms 65924 KB Output is correct
9 Correct 32 ms 65864 KB Output is correct
10 Correct 33 ms 65936 KB Output is correct
11 Correct 34 ms 65876 KB Output is correct
12 Correct 33 ms 65868 KB Output is correct
13 Correct 33 ms 65936 KB Output is correct
14 Correct 38 ms 65976 KB Output is correct
15 Correct 38 ms 65904 KB Output is correct
16 Correct 41 ms 65960 KB Output is correct
17 Correct 33 ms 65960 KB Output is correct
18 Correct 34 ms 65976 KB Output is correct
19 Correct 40 ms 65936 KB Output is correct
20 Correct 354 ms 67804 KB Output is correct
21 Correct 277 ms 67764 KB Output is correct
22 Correct 290 ms 67764 KB Output is correct
23 Correct 245 ms 68100 KB Output is correct
24 Correct 291 ms 67704 KB Output is correct
25 Correct 350 ms 67804 KB Output is correct
26 Correct 351 ms 67916 KB Output is correct
27 Correct 47 ms 66028 KB Output is correct
28 Correct 31 ms 65952 KB Output is correct
29 Correct 31 ms 65888 KB Output is correct
30 Correct 31 ms 65984 KB Output is correct
31 Correct 34 ms 65912 KB Output is correct
32 Correct 36 ms 65864 KB Output is correct
33 Correct 35 ms 65984 KB Output is correct
34 Correct 37 ms 65896 KB Output is correct
35 Correct 49 ms 66132 KB Output is correct
36 Correct 56 ms 65944 KB Output is correct
37 Correct 33 ms 65980 KB Output is correct
38 Correct 34 ms 65868 KB Output is correct
39 Correct 33 ms 65876 KB Output is correct
40 Correct 32 ms 65884 KB Output is correct
41 Correct 33 ms 65992 KB Output is correct
42 Correct 34 ms 65908 KB Output is correct
43 Correct 37 ms 65936 KB Output is correct
44 Correct 52 ms 65980 KB Output is correct
45 Correct 63 ms 66008 KB Output is correct
46 Correct 119 ms 66012 KB Output is correct
47 Correct 1872 ms 68544 KB Output is correct
48 Correct 904 ms 68116 KB Output is correct
49 Correct 865 ms 68188 KB Output is correct
50 Correct 1174 ms 69012 KB Output is correct
51 Correct 797 ms 68172 KB Output is correct
52 Correct 2181 ms 68812 KB Output is correct
53 Correct 2164 ms 69032 KB Output is correct
54 Correct 1055 ms 66736 KB Output is correct
55 Correct 749 ms 66832 KB Output is correct
56 Correct 933 ms 66492 KB Output is correct
57 Correct 703 ms 66476 KB Output is correct
58 Correct 1046 ms 66544 KB Output is correct
59 Execution timed out 4070 ms 69036 KB Time limit exceeded
60 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 65876 KB Output is correct
2 Correct 124 ms 66104 KB Output is correct
3 Correct 33 ms 65880 KB Output is correct
4 Correct 33 ms 65936 KB Output is correct
5 Execution timed out 4094 ms 65868 KB Time limit exceeded
6 Halted 0 ms 0 KB -