General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
84327280 Practice:
JKLover
986C - 13 GNU C++17 Accepted 1575 ms 111780 KB 2020-06-19 16:00:05 2020-06-19 16:00:05
 
 
→ Source
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int N = 1 << 23;
int n, m, U, a[N >> 1], b[N >> 1];
bool vis[N];
void dfs(int x)
{
	vis[x] = true;
	if (x < m)
	{
		if (!vis[m + a[x]])
			dfs(m + a[x]);
	}
	else
	{
		int S = x - m;
		for (int i = 0; i < n; ++i)
			if (!(S >> i & 1))
			{
				int y = m + (S | 1 << i);
				if (!vis[y])
					dfs(y);
			}
		if (b[U ^ S] && !vis[b[U ^ S] - 1])
			dfs(b[U ^ S] - 1);
	}
}
int main()
{
	n = read(), m = read();
	U = (1 << n) - 1;
	for (int i = 0; i < m; ++i)
	{
		a[i] = read();
		b[a[i]] = i + 1;
	}
	int ans = 0;
	for (int i = 0; i < m; ++i)
		if (!vis[i])
		{
			++ans;
			dfs(i);
		}
	write(ans, '\n');
	return 0;
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details