Submission #517194

#	Time	Username	Problem	Language	Result	Execution time	Memory
517194		raid	Norela (info1cup18_norela)	C++17	100 / 100	71 ms	300 KiB

norela

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

const int MAXM = 25;

using ll = long long;
#define bpc __builtin_popcount

ll v[MAXM], target;
int res_mask;
int m;

void backtrack( int idx, ll _xor, int mask ) {
  if ( idx == m ) {
    if ( _xor == target && (bpc(res_mask) > bpc(mask) || (bpc(res_mask) == bpc(mask) && res_mask < mask)) ) {  
	  res_mask = mask;
	}
	return;
  }
  backtrack( idx + 1, _xor, mask );
  backtrack( idx + 1, _xor ^ v[idx], mask + (1 << (m - idx - 1)) );
}

vector<int> sol;

int main() {
  int n, x, p;

  cin >> n >> m;
  res_mask = target = (1ll << n) - 1;
  for ( int i = 0; i < m; ++i ) {
	cin >> x;
	while (x--) {
      cin >> p;
	  v[i] += (1ll << (p-1));
	}
  }
  backtrack( 0, 0ll, 0 );
  for ( int i = 0; i < m; ++i ) {
	if ( res_mask & (1 << (m - i - 1)) ) {
      sol.push_back( i );	  
	}
  }
  cout << sol.size() << "\n";
  for ( int i = 0; i < sol.size(); ++i ) {
	cout << sol[i] + 1 << " ";
  }
  return 0;
}

Compilation message (stderr)

norela.cpp: In function 'int main()':
norela.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for ( int i = 0; i < sol.size(); ++i ) {
      |                    ~~^~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25