oj.uz

Submission #689933

# Submission time Handle Problem Language Result Execution time Memory
689933 2023-01-29T19:14:30 Z divad Norela (info1cup18_norela) C++14
75 / 100
 800 ms 320 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define int long long
#define NMAX 62
#define MMAX 26
using namespace std;
int n,m,q,x,ans,b[MMAX];
vector<int> sol;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    ans = 0;
    for(int i = 1; i <= m; i++){
        cin >> q;
        for(int j = 1; j <= q; j++){
            cin >> x;
            b[i] |= (1LL<<(x-1));
        }
    }
    for(int i = 0; i < (1<<m); i++){
        int all = 0;
        for(int j = 0; j < m; j++){
            if(i&(1LL<<j)){
                all ^= b[j+1];
            }
        }
        if(__builtin_popcountll(all) == n){
            if(ans == 0){
                ans = i;
                for(int j = 0; j < m; j++){
                    if(i&(1LL<<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&(1LL<<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&(1LL<<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;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 212 KB Output is correct
2 Correct 11 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 12 ms 212 KB Output is correct
5 Correct 12 ms 320 KB Output is correct
6 Correct 13 ms 320 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 212 KB Output is correct
2 Correct 11 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 12 ms 212 KB Output is correct
5 Correct 12 ms 320 KB Output is correct
6 Correct 13 ms 320 KB Output is correct
7 Correct 50 ms 300 KB Output is correct
8 Correct 95 ms 212 KB Output is correct
9 Correct 99 ms 300 KB Output is correct
10 Correct 96 ms 296 KB Output is correct
11 Correct 96 ms 296 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 212 KB Output is correct
2 Correct 11 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 12 ms 212 KB Output is correct
5 Correct 12 ms 320 KB Output is correct
6 Correct 13 ms 320 KB Output is correct
7 Correct 50 ms 300 KB Output is correct
8 Correct 95 ms 212 KB Output is correct
9 Correct 99 ms 300 KB Output is correct
10 Correct 96 ms 296 KB Output is correct
11 Correct 96 ms 296 KB Output is correct
12 Correct 94 ms 212 KB Output is correct
13 Correct 194 ms 296 KB Output is correct
14 Correct 191 ms 212 KB Output is correct
15 Correct 195 ms 296 KB Output is correct
16 Correct 194 ms 212 KB Output is correct
17 Correct 194 ms 312 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 212 KB Output is correct
2 Correct 11 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 12 ms 212 KB Output is correct
5 Correct 12 ms 320 KB Output is correct
6 Correct 13 ms 320 KB Output is correct
7 Correct 50 ms 300 KB Output is correct
8 Correct 95 ms 212 KB Output is correct
9 Correct 99 ms 300 KB Output is correct
10 Correct 96 ms 296 KB Output is correct
11 Correct 96 ms 296 KB Output is correct
12 Correct 94 ms 212 KB Output is correct
13 Correct 194 ms 296 KB Output is correct
14 Correct 191 ms 212 KB Output is correct
15 Correct 195 ms 296 KB Output is correct
16 Correct 194 ms 212 KB Output is correct
17 Correct 194 ms 312 KB Output is correct
18 Correct 387 ms 212 KB Output is correct
19 Correct 389 ms 304 KB Output is correct
20 Correct 800 ms 300 KB Output is correct
21 Execution timed out 807 ms 300 KB Time limit exceeded
22 Halted 0 ms 0 KB -