제출 #524613

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
524613		lucri	Norela (info1cup18_norela)	C++17	100 / 100	115 ms	332 KiB

norela

#include <iostream>
using namespace std;
long long p[65],n,m,nrmin=100,cmin[30],q,x,nr[30];
bool ver[30];
void bck(long long poz,long long ceva,long long folosit)
{
    if(poz==0)
    {
        if(ceva!=p[n]-1)
            return;
        if(folosit<nrmin)
        {
            nrmin=0;
            for(long long i=1;i<=m;++i)
            {
                if(ver[i]==true)
                    cmin[++nrmin]=i;
            }
        }
        else if(folosit == nrmin) {
            int p = 1;
            for(long long i = 1; i <= m; i++) {
                if(cmin[p] == i && ver[i] == false) {
                    return ;
                }
                if(cmin[p] > i && ver[i] == true) {

                    nrmin=0;
                    for(long long i=1;i<=m;++i)
                    {
                        if(ver[i]==true)
                            cmin[++nrmin]=i;
                    }
                    return ;
                }
                if(cmin[p] == i && ver[i] == true) {
                    p++;
                }
            }
        }
        return;
    }
    bck(poz-1,ceva,folosit);
    ceva^=nr[poz];
    ver[poz]=true;
    bck(poz-1,ceva,folosit+1);
    ceva^=nr[poz];
    ver[poz]=false;
    return;
}
int main()
{
    p[0]=1;
    for(long long i=1;i<=60;++i)
        p[i]=p[i-1]*2;
    cin>>n>>m;
    for(long long i=1;i<=m;++i)
    {
        cin>>q;
        for(long long j=1;j<=q;++j)
        {
            cin>>x;
            nr[i]+=p[x-1];
        }
    }
    bck(m,0,0);
    cout<<nrmin<<'\n';
    for(long long i=1;i<=nrmin;++i)
        cout<<cmin[i]<<' ';
    return 0;
}

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