Submission #674117

#	Time	Username	Problem	Language	Result	Execution time	Memory
674117		QwertyPi	Norela (info1cup18_norela)	C++14	100 / 100	3 ms	812 KiB

norela

#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 (stderr)

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 / 20
• Subtask 2: 30 / 30
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25