oj.uz

Submission #674113

# Submission time Handle Problem Language Result Execution time Memory
674113 2022-12-23T07:33:38 Z QwertyPi Norela (info1cup18_norela) C++14
0 / 100
 52 ms 788 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 & (1 << i)) != (b & (1 << i)))
			return (a & (1 << i)) > (b & (1 << 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 < (1 << n); i++){
		int v = 0;
		for(int j = 0; j < n; j++){
			if(i & (1 << 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 |= 1 << v - 1;
		}
		a.push_back(flip);
	}

	vector<int> a1, a2;
	for(int i = 0; i < min(m, 18LL); 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] << 18));
		}
	}
	int c = 0;
	for(int i = 0; i < m; i++){
		if(ans & (1 << i)) c++;
	}
	for(int i = 0; i < m; i++){
		if(ans & (1 << i)) cout << i + 1 << ' ';
	}
	cout << endl;
}

Compilation message

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

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 788 KB Output isn't correct
2 Halted 0 ms 0 KB -