oj.uz

Submission #689918

# Submission time Handle Problem Language Result Execution time Memory
689918 2023-01-29T18:36:11 Z divad Norela (info1cup18_norela) C++14
75 / 100
 800 ms 320 KB 
#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;
                    int ok = -1;
                    for(int j = 0; j < m; j++){
                        if(i&(1<<j)){
                            aux.push_back(j+1);
                            int pos = aux.size()-1;
                            if(ok == -1){
                                if(aux[pos] > sol[pos]){
                                    ok = 0;
                                }else if(aux[pos] < sol[pos]){
                                    ok = 1;
                                }
                            }
                        }
                    }
                    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

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){
      |            ~~~~~~~~~~~~^~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 212 KB Output is correct
2 Correct 16 ms 312 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 16 ms 316 KB Output is correct
5 Correct 18 ms 320 KB Output is correct
6 Correct 16 ms 212 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 212 KB Output is correct
2 Correct 16 ms 312 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 16 ms 316 KB Output is correct
5 Correct 18 ms 320 KB Output is correct
6 Correct 16 ms 212 KB Output is correct
7 Correct 59 ms 212 KB Output is correct
8 Correct 114 ms 292 KB Output is correct
9 Correct 121 ms 296 KB Output is correct
10 Correct 118 ms 292 KB Output is correct
11 Correct 117 ms 292 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 212 KB Output is correct
2 Correct 16 ms 312 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 16 ms 316 KB Output is correct
5 Correct 18 ms 320 KB Output is correct
6 Correct 16 ms 212 KB Output is correct
7 Correct 59 ms 212 KB Output is correct
8 Correct 114 ms 292 KB Output is correct
9 Correct 121 ms 296 KB Output is correct
10 Correct 118 ms 292 KB Output is correct
11 Correct 117 ms 292 KB Output is correct
12 Correct 115 ms 292 KB Output is correct
13 Correct 249 ms 292 KB Output is correct
14 Correct 242 ms 212 KB Output is correct
15 Correct 237 ms 212 KB Output is correct
16 Correct 249 ms 300 KB Output is correct
17 Correct 236 ms 292 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 212 KB Output is correct
2 Correct 16 ms 312 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 16 ms 316 KB Output is correct
5 Correct 18 ms 320 KB Output is correct
6 Correct 16 ms 212 KB Output is correct
7 Correct 59 ms 212 KB Output is correct
8 Correct 114 ms 292 KB Output is correct
9 Correct 121 ms 296 KB Output is correct
10 Correct 118 ms 292 KB Output is correct
11 Correct 117 ms 292 KB Output is correct
12 Correct 115 ms 292 KB Output is correct
13 Correct 249 ms 292 KB Output is correct
14 Correct 242 ms 212 KB Output is correct
15 Correct 237 ms 212 KB Output is correct
16 Correct 249 ms 300 KB Output is correct
17 Correct 236 ms 292 KB Output is correct
18 Correct 507 ms 296 KB Output is correct
19 Correct 495 ms 300 KB Output is correct
20 Execution timed out 1055 ms 212 KB Time limit exceeded
21 Halted 0 ms 0 KB -