Submission #1289717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289717		dirtblock	Norela (info1cup18_norela)	C++20	0 / 100	5 ms	444 KiB

norela

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n,m;
vector<int> a(3005,0);
int mn=LLONG_MAX;
vector<int> ans,cur;

void find(int x,int p) {
	if(x==m) {
		if(p==pow(2,n)-1&&(int)cur.size()<mn) {
			mn=cur.size();
			ans=cur;
		}
		if((int)cur.size()==mn) {
			for(int i=0; i<mn; i++) {
				if(cur[i]<ans[i]) {
					ans=cur;
					break;
				}
				if(ans[i]>cur[i]) break;
			}
		}
		return;
	}
	find(x+1,p);
	cur.push_back(x);
	find(x+1,p^a[x]);
	cur.pop_back();
}

signed main() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin>>n>>m;
	a.resize(m);
	for(int i=0; i<m; i++) {
		int x; cin>>x;
		for(int j=0; j<x; j++) {
			int g; cin>>g;
			a[i]+=pow(2,g-1);
		}
	}
	find(0,0);
	cout<<mn<<"\n";
	for(int x:ans) cout<<x+1<<" ";
	
	return 0;
}

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