oj.uz

Submission #689914

# Submission time Handle Problem Language Result Execution time Memory
689914 2023-01-29T18:01:46 Z divad Norela (info1cup18_norela) C++14
75 / 100
 800 ms 340 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;
                    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

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.0 / 20.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 320 KB Output is correct
2 Correct 15 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 15 ms 340 KB Output is correct
5 Correct 15 ms 320 KB Output is correct
6 Correct 15 ms 316 KB Output is correct
7 Correct 58 ms 212 KB Output is correct
8 Correct 119 ms 296 KB Output is correct
9 Correct 126 ms 296 KB Output is correct
10 Correct 124 ms 300 KB Output is correct
11 Correct 112 ms 212 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 320 KB Output is correct
2 Correct 15 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 15 ms 340 KB Output is correct
5 Correct 15 ms 320 KB Output is correct
6 Correct 15 ms 316 KB Output is correct
7 Correct 58 ms 212 KB Output is correct
8 Correct 119 ms 296 KB Output is correct
9 Correct 126 ms 296 KB Output is correct
10 Correct 124 ms 300 KB Output is correct
11 Correct 112 ms 212 KB Output is correct
12 Correct 117 ms 304 KB Output is correct
13 Correct 252 ms 308 KB Output is correct
14 Correct 242 ms 336 KB Output is correct
15 Correct 234 ms 304 KB Output is correct
16 Correct 239 ms 212 KB Output is correct
17 Correct 237 ms 332 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 320 KB Output is correct
2 Correct 15 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 15 ms 340 KB Output is correct
5 Correct 15 ms 320 KB Output is correct
6 Correct 15 ms 316 KB Output is correct
7 Correct 58 ms 212 KB Output is correct
8 Correct 119 ms 296 KB Output is correct
9 Correct 126 ms 296 KB Output is correct
10 Correct 124 ms 300 KB Output is correct
11 Correct 112 ms 212 KB Output is correct
12 Correct 117 ms 304 KB Output is correct
13 Correct 252 ms 308 KB Output is correct
14 Correct 242 ms 336 KB Output is correct
15 Correct 234 ms 304 KB Output is correct
16 Correct 239 ms 212 KB Output is correct
17 Correct 237 ms 332 KB Output is correct
18 Correct 539 ms 304 KB Output is correct
19 Correct 490 ms 340 KB Output is correct
20 Execution timed out 1041 ms 304 KB Time limit exceeded
21 Halted 0 ms 0 KB -