Submission #689914

#	Time	Username	Problem	Language	Result	Execution time	Memory
689914		divad	Norela (info1cup18_norela)	C++14	75 / 100	1041 ms	340 KiB

norela

#include <bits/stdc++.h>
#define int long long
#define NMAX 62
#define MMAX 26
using namespace std;
int n,m,q,x,ans;
bitset<NMAX> b[MMAX];
vector<int> sol;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    ans = -1;
    for(int i = 1; i <= m; i++){
        cin >> q;
        for(int j = 1; j <= q; j++){
            cin >> x;
            b[i][x] = 1;
        }
    }
    for(int i = 0; i < (1<<m); i++){
        bitset<NMAX> all;
        for(int j = 0; j < m; j++){
            if(i&(1<<j)){
                all ^= b[j+1];
            }
        }
        if(all.count() == n){
            if(ans == -1){
                ans = i;
                for(int j = 0; j < m; j++){
                    if(i&(1<<j)){
                        sol.push_back(j+1);
                    }
                }
            }else{
                if(__builtin_popcount(ans) > __builtin_popcount(i)){
                    sol.clear();
                    for(int j = 0; j < m; j++){
                        if(i&(1<<j)){
                            sol.push_back(j+1);
                        }
                    }
                    ans = i;
                }else if(__builtin_popcount(ans) == __builtin_popcount(i)){
                    vector<int> aux;
                    for(int j = 0; j < m; j++){
                        if(i&(1<<j)){
                            aux.push_back(j+1);
                        }
                    }
                    bool ok = true;
                    for(int j = 0; j < sol.size(); j++){
                        if(aux[j] > sol[j]){
                            ok = false;
                            break;
                        }else if(aux[j] < sol[j]){
                            ok = true;
                            break;
                        }
                    }
                    if(ok){
                        sol.clear();
                        for(auto it: aux){
                            sol.push_back(it);
                        }
                        ans = i;
                    }
                }
            }
        }
    }
    cout << __builtin_popcount(ans) << "\n";
    for(auto it: sol){
        cout << it << " ";
    }
    return 0;
}

Compilation message (stderr)

norela.cpp: In function 'int main()':
norela.cpp:30:24: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   30 |         if(all.count() == n){
      |            ~~~~~~~~~~~~^~~~
norela.cpp:55:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |                     for(int j = 0; j < sol.size(); j++){
      |                                    ~~^~~~~~~~~~~~

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