oj.uz

Submission #204985

# Submission time Handle Problem Language Result Execution time Memory
204985 2020-02-27T15:49:14 Z Haunted_Cpp Norela (info1cup18_norela) C++17
75 / 100
 800 ms 508 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) {
    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 23 ms 376 KB Output is correct
2 Correct 23 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 23 ms 376 KB Output is correct
5 Correct 23 ms 376 KB Output is correct
6 Correct 23 ms 376 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 376 KB Output is correct
2 Correct 23 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 23 ms 376 KB Output is correct
5 Correct 23 ms 376 KB Output is correct
6 Correct 23 ms 376 KB Output is correct
7 Correct 78 ms 376 KB Output is correct
8 Correct 156 ms 504 KB Output is correct
9 Correct 152 ms 420 KB Output is correct
10 Correct 154 ms 376 KB Output is correct
11 Correct 156 ms 504 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 376 KB Output is correct
2 Correct 23 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 23 ms 376 KB Output is correct
5 Correct 23 ms 376 KB Output is correct
6 Correct 23 ms 376 KB Output is correct
7 Correct 78 ms 376 KB Output is correct
8 Correct 156 ms 504 KB Output is correct
9 Correct 152 ms 420 KB Output is correct
10 Correct 154 ms 376 KB Output is correct
11 Correct 156 ms 504 KB Output is correct
12 Correct 159 ms 504 KB Output is correct
13 Correct 313 ms 388 KB Output is correct
14 Correct 315 ms 504 KB Output is correct
15 Correct 315 ms 376 KB Output is correct
16 Correct 310 ms 376 KB Output is correct
17 Correct 310 ms 504 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 376 KB Output is correct
2 Correct 23 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 23 ms 376 KB Output is correct
5 Correct 23 ms 376 KB Output is correct
6 Correct 23 ms 376 KB Output is correct
7 Correct 78 ms 376 KB Output is correct
8 Correct 156 ms 504 KB Output is correct
9 Correct 152 ms 420 KB Output is correct
10 Correct 154 ms 376 KB Output is correct
11 Correct 156 ms 504 KB Output is correct
12 Correct 159 ms 504 KB Output is correct
13 Correct 313 ms 388 KB Output is correct
14 Correct 315 ms 504 KB Output is correct
15 Correct 315 ms 376 KB Output is correct
16 Correct 310 ms 376 KB Output is correct
17 Correct 310 ms 504 KB Output is correct
18 Correct 638 ms 504 KB Output is correct
19 Correct 640 ms 508 KB Output is correct
20 Execution timed out 1094 ms 376 KB Time limit exceeded
21 Halted 0 ms 0 KB -