Submission #1134117

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134117		bpptidp	Norela (info1cup18_norela)	C++20	0 / 100	27 ms	33348 KiB

norela

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

using ll=long long;

int n,m;
vector<int>ans;
vector<int>sp[27],koji[66],nemaju[66];
ll bsp[26],b;

bool losi[(1<<25)],imao[(1<<25)];

bool bolje(const bitset<25>a,const bitset<25>b){
	int c1=a.count();
	int c2=b.count();
	if(c1>c2)return 0;
	if(c1<c2)return 1;
	for(int i=0;i<a.size();++i){
		if(a[i]>b[i])return 1;
		if(a[i]<b[i])return 0;
	}
	return 0;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>m;

    bitset<66>bb;
    for(int i=0,q,x;i<m;++i){
    	cin>>q;
    	bb=0;
    	while(q--){
    		cin>>x;
    		sp[i].push_back(x);
    		koji[x].push_back(i);
    		bsp[i]+=(1<<x);
    		bb[x]=1;
    	}
    	for(int j=1;j<=n;++j){
    		if(!bb[j])nemaju[j].push_back(i);
    	}
    }

    for(int x=1;x<=n;++x){
    	int msk=0;
    	for(int i:koji[x])
    		msk^=(1<<i);
    	if(imao[msk])continue;
    	imao[msk]=1;
    	for(int s=msk;s;s=(s-1)&msk)
    		if(__builtin_popcount(s)&1^1)losi[s]=1;
    }

    fill(imao,imao+(1<<25),0);

    for(int x=1;x<=n;++x){
    	int msk=0;
    	for(int i:nemaju[x])
    		msk^=(1<<i);
    	if(imao[msk])continue;
    	imao[msk]=1;
    	for(int s=msk;s;s=(s-1)&msk)losi[s]=1;
    }

    bitset<25>ans,nw;
    for(int i=0;i<m;++i)
    	ans[i]=1;

    for(int msk=1;msk<(1<<m);++msk){
    	if(losi[msk])continue;
    	b=0;
    	for(int i=0;i<m;++i)
    		if(msk&(1<<i))b^=bsp[i];
    	if(__builtin_popcount(b)!=n)continue;
    	nw=0;
    	for(int j=0;j<m;++j)
    		nw[j]=((msk&(1<<j))!=0);
    	if(bolje(nw,ans))ans=nw;
    }

    cout<<ans.count()<<'\n';
    for(int i=0;i<m;++i)
    	if(ans[i])cout<<i+1<<' ';
}

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