oj.uz

Submission #204987

# Submission time Handle Problem Language Result Execution time Memory
204987 2020-02-27T15:51:52 Z Haunted_Cpp Norela (info1cup18_norela) C++17
100 / 100
 596 ms 504 KB 
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <algorithm>
#include <cstring>
#include <cassert>
#include <bitset>
using namespace std;
 
#define FOR(i, a, b) for (int i = a; i < (int) b; i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = a; i >= (int) b; i--)
#define R0F(i, a) ROF(i, a, 0)
#define GO(i, a) for (auto i : a)
 
#define f first
#define s second
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef vector<vpii> vvpii;
typedef long long i64;
typedef vector<i64> vi64;
 
const int dr[] = {+1, -1, +0, +0, +1, -1, +1, -1};
const int dc[] = {+0, +0, +1, -1, +1, -1, -1, +1};
const int ms[] = {+31, +29, +31, 30, +31, +30, +31, +31, +30, +31, +30, +31};

void setIO(string nome) {
  ios_base::sync_with_stdio(0); cin.tie(0);
  freopen ((nome + ".in").c_str(), "r", stdin);
  freopen ((nome + ".out").c_str(), "w", stdout);
}

int main () {
  ios_base::sync_with_stdio(0); 
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<i64> q (m);
  F0R (i, m) {
    int foo;
    cin >> foo;
    i64 mask = 0;
    F0R (j, foo) {
      int bar;
      cin >> bar;
      --bar;
      mask |= (1LL << bar);
    }
    q[i] = mask;
  }
  i64 ans = (1LL << 60) - 1;
  i64 Get = 0;
  F0R (mask, 1 << m) {
    if (__builtin_popcountll(mask) > __builtin_popcountll(ans)) continue;
    Get = 0;
    F0R (i, m) {
      if ((mask >> i) & 1) {
        Get ^= q[i];
      }
    }
    if (__builtin_popcountll(Get) == n) {
      if (__builtin_popcountll(mask) == __builtin_popcountll(ans)) {
        F0R (i, m) {
          int A = ((ans >> i) & 1);
          int B = ((mask >> i) & 1);
          if (A && !B) {
            break;
          }
          if (B && !A) {
            ans = mask;
            break;
          }
        }
        continue;
      }
      if (__builtin_popcountll(mask) < __builtin_popcountll(ans)) ans = mask;
    }
  }
  cout << __builtin_popcountll(ans) << '\n';
  F0R (i, m) {
    if ((ans >> i) & 1) cout << i + 1 << ' ';
  }
  cout << '\n';
  return 0;
}

Compilation message

norela.cpp: In function 'void setIO(std::__cxx11::string)':
norela.cpp:39:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen ((nome + ".in").c_str(), "r", stdin);
   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
norela.cpp:40:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen ((nome + ".out").c_str(), "w", stdout);
   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 376 KB Output is correct
2 Correct 9 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 12 ms 376 KB Output is correct
5 Correct 7 ms 376 KB Output is correct
6 Correct 10 ms 376 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 376 KB Output is correct
2 Correct 9 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 12 ms 376 KB Output is correct
5 Correct 7 ms 376 KB Output is correct
6 Correct 10 ms 376 KB Output is correct
7 Correct 11 ms 376 KB Output is correct
8 Correct 76 ms 504 KB Output is correct
9 Correct 95 ms 376 KB Output is correct
10 Correct 34 ms 376 KB Output is correct
11 Correct 16 ms 376 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 376 KB Output is correct
2 Correct 9 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 12 ms 376 KB Output is correct
5 Correct 7 ms 376 KB Output is correct
6 Correct 10 ms 376 KB Output is correct
7 Correct 11 ms 376 KB Output is correct
8 Correct 76 ms 504 KB Output is correct
9 Correct 95 ms 376 KB Output is correct
10 Correct 34 ms 376 KB Output is correct
11 Correct 16 ms 376 KB Output is correct
12 Correct 43 ms 376 KB Output is correct
13 Correct 260 ms 504 KB Output is correct
14 Correct 150 ms 376 KB Output is correct
15 Correct 30 ms 380 KB Output is correct
16 Correct 101 ms 380 KB Output is correct
17 Correct 41 ms 376 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 376 KB Output is correct
2 Correct 9 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 12 ms 376 KB Output is correct
5 Correct 7 ms 376 KB Output is correct
6 Correct 10 ms 376 KB Output is correct
7 Correct 11 ms 376 KB Output is correct
8 Correct 76 ms 504 KB Output is correct
9 Correct 95 ms 376 KB Output is correct
10 Correct 34 ms 376 KB Output is correct
11 Correct 16 ms 376 KB Output is correct
12 Correct 43 ms 376 KB Output is correct
13 Correct 260 ms 504 KB Output is correct
14 Correct 150 ms 376 KB Output is correct
15 Correct 30 ms 380 KB Output is correct
16 Correct 101 ms 380 KB Output is correct
17 Correct 41 ms 376 KB Output is correct
18 Correct 75 ms 376 KB Output is correct
19 Correct 71 ms 376 KB Output is correct
20 Correct 596 ms 504 KB Output is correct
21 Correct 381 ms 376 KB Output is correct
22 Correct 277 ms 504 KB Output is correct
23 Correct 119 ms 376 KB Output is correct