oj.uz

Submission #923457

# Submission time Handle Problem Language Result Execution time Memory
923457 2024-02-07T09:12:54 Z NValchanov Norela (info1cup18_norela) C++17
75 / 100
 800 ms 600 KB 
#include<bits/stdc++.h>

#define endl '\n'

using namespace std;

typedef long long ll;

const ll MAXN=64;
const ll MAXM=25;

ll a[MAXN],n,m,q,c;
ll ans;
vector<ll>order;

void read()
{
    cin>>n>>m;
    for(ll i=0;i<m;i++)
    {
        cin>>q;
        for(ll j=0;j<q;j++)
        {
            cin>>c;
            a[i]|=(ll)(1LL<<(c-1));
        }
    }
}

ll count_bits(ll mask)
{
    ll cnt=0;
    for(ll i=0;i<n;i++)
    {
        if(mask&(1LL<<i))
            cnt++;
    }
    return cnt;
}

void fill_order(ll mask)
{
    order.clear();
    ans=mask;
    for(ll i=0;i<m;i++)
    {
        if(mask&(1LL<<(i)))
        {
            order.push_back(i+1);
        }
    }
}

void check_current(ll mask, ll x)
{
    if(count_bits(x) == n)
    {
        if(!ans)
            fill_order(mask);
        else
        {
            if(count_bits(ans)>count_bits(mask))
                fill_order(mask);
            else if(count_bits(ans)==count_bits(mask))
            {
                ll lampa=-1;
                vector<ll>tmp;
                for(ll i=0;i<m;i++)
                {
                    if(mask&(1LL<<i))
                    {
                        tmp.push_back(i+1);
                        ll sz=tmp.size();
                        if(lampa==-1)
                        {
                            if(tmp[sz-1]>order[sz-1])
                                lampa=0;
                            else if(tmp[sz-1]<order[sz-1])
                                lampa=1;
                        }
                    }
                }
                if(lampa==1)
                {
                    ans=mask;
                    order.clear();
                    order=tmp;
                }
            }
        }
    }
}

void solve()
{
    ans=0;
    for(ll mask=0;mask<(1LL<<m);mask++)
    {
        ll cur=0;
        for(ll i=0;i<m;i++)
        {
            if(mask&(1LL<<i))
            {
                cur^=a[i];
            }
        }
        check_current(mask, cur);
    }
}

void print()
{
    ll sz=count_bits(ans);
    cout<<sz<<endl;
    for(ll i=0;i<sz;i++)
    {
        cout<<order[i]<<" ";
    }
    cout<<endl;
}

int main()
{
    #ifdef ONLINE_JUDGE
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

    read();
    solve();
    print();

	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 348 KB Output is correct
2 Correct 23 ms 456 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 24 ms 348 KB Output is correct
5 Correct 22 ms 344 KB Output is correct
6 Correct 23 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 348 KB Output is correct
2 Correct 23 ms 456 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 24 ms 348 KB Output is correct
5 Correct 22 ms 344 KB Output is correct
6 Correct 23 ms 348 KB Output is correct
7 Correct 111 ms 344 KB Output is correct
8 Correct 226 ms 428 KB Output is correct
9 Correct 226 ms 432 KB Output is correct
10 Correct 197 ms 432 KB Output is correct
11 Correct 194 ms 348 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 348 KB Output is correct
2 Correct 23 ms 456 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 24 ms 348 KB Output is correct
5 Correct 22 ms 344 KB Output is correct
6 Correct 23 ms 348 KB Output is correct
7 Correct 111 ms 344 KB Output is correct
8 Correct 226 ms 428 KB Output is correct
9 Correct 226 ms 432 KB Output is correct
10 Correct 197 ms 432 KB Output is correct
11 Correct 194 ms 348 KB Output is correct
12 Correct 237 ms 428 KB Output is correct
13 Correct 468 ms 432 KB Output is correct
14 Correct 459 ms 432 KB Output is correct
15 Correct 469 ms 432 KB Output is correct
16 Correct 467 ms 344 KB Output is correct
17 Correct 474 ms 600 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 348 KB Output is correct
2 Correct 23 ms 456 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 24 ms 348 KB Output is correct
5 Correct 22 ms 344 KB Output is correct
6 Correct 23 ms 348 KB Output is correct
7 Correct 111 ms 344 KB Output is correct
8 Correct 226 ms 428 KB Output is correct
9 Correct 226 ms 432 KB Output is correct
10 Correct 197 ms 432 KB Output is correct
11 Correct 194 ms 348 KB Output is correct
12 Correct 237 ms 428 KB Output is correct
13 Correct 468 ms 432 KB Output is correct
14 Correct 459 ms 432 KB Output is correct
15 Correct 469 ms 432 KB Output is correct
16 Correct 467 ms 344 KB Output is correct
17 Correct 474 ms 600 KB Output is correct
18 Execution timed out 963 ms 600 KB Time limit exceeded
19 Halted 0 ms 0 KB -