fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4.  
  5. using namespace std;
  6.  
  7. using pii = pair<int, int>;
  8.  
  9. const int M = 22;
  10. const int N = (1 << M);
  11.  
  12. int a[N + 5], id[N + 5];
  13. bool visited[2 * N + 5];
  14. int n, m, all;
  15.  
  16. void dfs(int u) {
  17.     visited[u] = true;
  18.  
  19.     if (u < n) {
  20.         int v = a[u] + n;
  21.         if (!visited[v]) dfs(v);
  22.     }
  23.     else {
  24.         int mask = u - n;
  25.         for (int id = 0; id < m; id++)
  26.             if (!(mask >> id & 1)) {
  27.                 int v = (mask | (1 << id)) + n;
  28.                 if (!visited[v]) dfs(v);
  29.             }
  30.  
  31.         mask = all - mask;
  32.  
  33.         if(id[mask] != -1) {
  34.             int v = id[mask];
  35.             if (!visited[v]) dfs(v);
  36.         }
  37.     }
  38. }
  39.  
  40. void solve() {
  41.     cin >> m >> n;
  42.  
  43.     memset(id, -1, sizeof(id));
  44.  
  45.     for (int i = 0; i < n; i++) {
  46.         cin >> a[i];
  47.         id[a[i]] = i;
  48.     }
  49.  
  50.     all = (1 << m) - 1;
  51.  
  52.     int cpn = 0;
  53.  
  54.     for (int i = 0; i < n; i++)
  55.         if (!visited[i]) {
  56.             dfs(i);
  57.             ++cpn;
  58.         }
  59.  
  60.     cout << cpn;
  61. }
  62.  
  63. int main() {
  64.     ios_base::sync_with_stdio(false);
  65.     cin.tie(0); cout.tie(0);
  66.     solve();
  67.     return 0;
  68. }
  69.  
Success #stdin #stdout 0.01s 21960KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mTIk91
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!