oj.uz

Submission #674117

# Submission time Handle Problem Language Result Execution time Memory
674117 2022-12-23T08:08:39 Z QwertyPi Norela (info1cup18_norela) C++14
100 / 100
 3 ms 812 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

bool be(int a, int b){
	if(a == -1 || b == -1) return a != -1;
	if(__builtin_popcountll(a) != __builtin_popcountll(b))
		return __builtin_popcountll(a) < __builtin_popcountll(b);
	for(int i = 0;; i++){
		if((a & (1LL << i)) != (b & (1LL << i)))
			return (a & (1LL << i)) > (b & (1LL << i));
	}
	assert(0);
	return false;
}

map<int, int> gen(int l, vector<int> a){
	map<int, int> M;
	int n = a.size();
	for(int i = 1; i < (1LL << n); i++){
		int v = 0;
		for(int j = 0; j < n; j++){
			if(i & (1LL << j)) v ^= a[j];
		}
		if(M.count(v) == 0 || be(i, M[v])) M[v] = i;
	}
	return M;
}

int ok(int x, int y){
	return be(x, y) ? x : y;
}

int32_t main() {
	int n, m; cin >> n >> m;
	vector<int> a;
	for(int i = 0; i < m; i++){
		int k; cin >> k; int flip = 0;
		for(int j = 0; j < k; j++){
			int v; cin >> v; flip |= 1LL << v - 1;
		}
		a.push_back(flip);
	}

	vector<int> a1, a2;
	for(int i = 0; i < min(m, 12LL); i++){
		a1.push_back(a[i]);
	}
	for(int i = 12; i < min(m, 24LL); i++){
		a2.push_back(a[i]);
	}
	map<int, int> m1 = gen(0, a1), m2 = gen(a1.size(), a2);

	int ans = -1;
	int sum = (1LL << n) - 1;
	if(m1.count(sum)) ans = ok(ans, m1[sum]);
	if(m2.count(sum)) ans = ok(ans, m2[sum]);
	for(auto i : m1){
		int v = i.first, s = i.second;
		if(m2.count(sum - v)){
			ans = ok(ans, s | (m2[sum - v] << 12));
		}
	}
	int c = 0;
	for(int i = 0; i < m; i++){
		if(ans & (1LL << i)) c++;
	}
	cout << c << endl;
	for(int i = 0; i < m; i++){
		if(ans & (1LL << i)) cout << i + 1 << ' ';
	}
	cout << endl;
}

Compilation message

norela.cpp: In function 'int32_t main()':
norela.cpp:40:38: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   40 |    int v; cin >> v; flip |= 1LL << v - 1;
      |                                    ~~^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 468 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 560 KB Output is correct
9 Correct 2 ms 556 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 468 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 560 KB Output is correct
9 Correct 2 ms 556 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 552 KB Output is correct
13 Correct 2 ms 556 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 3 ms 556 KB Output is correct
17 Correct 2 ms 596 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 560 KB Output is correct
9 Correct 2 ms 556 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 552 KB Output is correct
13 Correct 2 ms 556 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 3 ms 556 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 3 ms 684 KB Output is correct
19 Correct 3 ms 596 KB Output is correct
20 Correct 3 ms 724 KB Output is correct
21 Correct 3 ms 724 KB Output is correct
22 Correct 3 ms 724 KB Output is correct
23 Correct 3 ms 812 KB Output is correct