QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#427721#8770. Comparatorucup-team987#AC ✓49ms22072kbC++204.5kb2024-06-01 15:14:222024-06-01 15:14:22

Judging History

你现在查看的是最新测评结果

  • [2024-06-01 15:14:22]
  • 评测
  • 测评结果:AC
  • 用时:49ms
  • 内存:22072kb
  • [2024-06-01 15:14:22]
  • 提交

answer

#include<iostream>
#include<bitset>
#include<cassert>
using namespace std;
void disp(int v,int k)
{
	for(int i=0;i<k;i++)cout<<(v>>i&1);
	cout<<endl;
}
string S;
int eval(int&);
int atom(int&idx)
{
	assert(idx<S.size());
	char c=S[idx++];
	bool NOT=false;
	while(c=='!')
	{
		NOT=!NOT;
		c=S[idx++];
	}
	int ret;
	if(c=='(')
	{
		ret=eval(idx);
		assert(S[idx]==')');
		idx++;
	}
	else if(c=='0')ret=0b0000;
	else if(c=='1')ret=0b1111;
	else if(c=='x')ret=0b1100;
	else if(c=='y')ret=0b1010;
	else assert(false);
	if(NOT)ret^=0b1111;
	return ret;
}
int EQ(int&idx)
{
	int ret=atom(idx);
	while(S[idx]=='=')
	{
		idx++;
		int nxt=atom(idx);
		ret=(ret^nxt)^0b1111;
	}
	return ret;
}
int AND(int&idx)
{
	int ret=EQ(idx);
	while(S[idx]=='&')
	{
		idx++;
		int nxt=EQ(idx);
		ret=ret&nxt;
	}
	return ret;
}
int OR(int&idx)
{
	int ret=AND(idx);
	while(S[idx]=='|')
	{
		idx++;
		int nxt=AND(idx);
		ret=ret|nxt;
	}
	return ret;
}
int eval(int&idx)
{//xor
	int ret=OR(idx);
	while(S[idx]=='^')
	{
		idx++;
		int nxt=OR(idx);
		ret^=nxt;
	}
	return ret;
}
int N,K;
int a[2<<17],b[2<<17],r[2<<17],F[2<<17];
int R;
int tb[1<<10][1<<10];
void Fill(int r,int X,int rX,int Y,int rY)
{
	for(int x=rX;x>=0;x--)
	{
		x&=rX;
		for(int y=rY;y>=0;y--)
		{
			y&=rY;
			tb[X|x][Y|y]=r;
		}
	}
}
void dfs(int id,int X,int rX,int Y,int rY)
{
	if(id==N)
	{
		Fill(R,X,rX,Y,rY);
		return;
	}
	if(rX>>a[id]&1)
	{
		if(rY>>b[id]&1)
		{
			int ok=0;
			for(int x=0;x<2;x++)for(int y=0;y<2;y++)
			{
				if(F[id]>>x*2+y&1)Fill(r[id],X|x<<a[id],rX^1<<a[id],Y|y<<b[id],rY^1<<b[id]);
				else ok|=1<<x*2+y;
			}
			assert(0b0000<=ok&&ok<=0b1111);
			if(ok==0b1111)dfs(id+1,X,rX,Y,rY);
			else if(ok==0b0110)
			{
				dfs(id+1,X|1<<a[id],rX^1<<a[id],Y,rY^1<<b[id]);
				dfs(id+1,X,rX^1<<a[id],Y|1<<b[id],rY^1<<b[id]);
			}
			else if(ok==0b1001)
			{
				dfs(id+1,X,rX^1<<a[id],Y,rY^1<<b[id]);
				dfs(id+1,X|1<<a[id],rX^1<<a[id],Y|1<<b[id],rY^1<<b[id]);
			}
			else
			{
				if((ok&0b0011)==0b0011)
				{//x=0,y=01
					dfs(id+1,X,rX^1<<a[id],Y,rY);
					ok^=0b0011;
				}
				if((ok&0b1100)==0b1100)
				{//x=1,y=01
					dfs(id+1,X|1<<a[id],rX^1<<a[id],Y,rY);
					ok^=0b1100;
				}
				if((ok&0b0101)==0b0101)
				{//x=01,y=0
					dfs(id+1,X,rX,Y,rY^1<<b[id]);
					ok^=0b0101;
				}
				if((ok&0b1010)==0b1010)
				{//x=01,y=1
					dfs(id+1,X,rX,Y|1<<b[id],rY^1<<b[id]);
					ok^=0b1010;
				}
				if(ok==0b0001)
				{//x=0,y=0
					dfs(id+1,X,rX^1<<a[id],Y,rY^1<<b[id]);
				}
				else if(ok==0b0010)
				{//x=0,y=1
					dfs(id+1,X,rX^1<<a[id],Y|1<<b[id],rY^1<<b[id]);
				}
				else if(ok==0b0100)
				{//x=1,y=0
					dfs(id+1,X|1<<a[id],rX^1<<a[id],Y,rY^1<<b[id]);
				}
				else if(ok==0b1000)
				{//x=1,y=1
					dfs(id+1,X|1<<a[id],rX^1<<a[id],Y|1<<b[id],rY^1<<b[id]);
				}
				else assert(ok==0b0000);
			}
		}
		else
		{
			int y=Y>>b[id]&1;
			int ok=0;
			for(int x=0;x<2;x++)
			{
				if(F[id]>>x*2+y&1)Fill(r[id],X|x<<a[id],rX^1<<a[id],Y,rY);
				else ok|=1<<x;
			}
			assert(0b00<=ok&&ok<=0b11);
			if(ok==0b11)dfs(id+1,X,rX,Y,rY);
			else if(ok==0b01)dfs(id+1,X,rX^1<<a[id],Y,rY);
			else if(ok==0b10)dfs(id+1,X|1<<a[id],rX^1<<a[id],Y,rY);
		}
	}
	else
	{
		if(rY>>b[id]&1)
		{
			int x=X>>a[id]&1;
			int ok=0;
			for(int y=0;y<2;y++)
			{
				if(F[id]>>x*2+y&1)Fill(r[id],X,rX,Y|y<<b[id],rY^1<<b[id]);
				else ok|=1<<y;
			}
			assert(0b00<=ok&&ok<=0b11);
			if(ok==0b11)dfs(id+1,X,rX,Y,rY);
			else if(ok==0b01)dfs(id+1,X,rX,Y,rY^1<<b[id]);
			else if(ok==0b10)dfs(id+1,X,rX,Y|1<<b[id],rY^1<<b[id]);
		}
		else
		{
			int x=X>>a[id]&1,y=Y>>b[id]&1;
			if(F[id]>>x*2+y&1)Fill(r[id],X,rX,Y,rY);
			else dfs(id+1,X,rX,Y,rY);
		}
	}
}
bitset<1<<10>H[1<<10],W[1<<10];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>N>>K;
	for(int i=0;i<N;i++)
	{
		cin>>a[i]>>b[i]>>S>>r[i];
		a[i]--,b[i]--;
		int idx=0;
		F[i]=eval(idx);
		assert(idx==S.size());
	}
	cin>>R;
	for(int i=0;i<1<<K;i++)for(int j=0;j<1<<K;j++)tb[i][j]=-1;
	dfs(0,0,(1<<K)-1,0,(1<<K)-1);
	for(int i=0;i<1<<K;i++)for(int j=0;j<1<<K;j++)
	{
		assert(tb[i][j]!=-1);
		if(tb[i][j]==1)
		{
			H[i].set(j);
			W[j].set(i);
		}
	}
	int ans[3]={};
	for(int i=0;i<1<<K;i++)
	{
		if(tb[i][i]==1)ans[0]++;
		for(int j=0;j<1<<K;j++)
		{
			if(tb[i][j]==1&&tb[j][i]==1)ans[1]++;
			if(tb[i][j]==0)ans[2]+=(H[i]&W[j]).count();
		}
	}
	cout<<ans[0]<<" "<<ans[1]<<" "<<ans[2]<<endl;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 9768kb

input:

3 2
1 1 (x=0)&(y=1) 1
1 1 (x=1)&(y=(x^x)) 0
2 2 (x=1)|(y=0) 0
1

output:

0 0 0

result:

ok single line: '0 0 0'

Test #2:

score: 0
Accepted
time: 0ms
memory: 9704kb

input:

4 3
2 1 x=0&(y=1) 1
1 2 !x^!!y 0
2 3 ((x|1)=y)&1&1 1
3 1 !x&!x&!x 0
1

output:

3 25 52

result:

ok single line: '3 25 52'

Test #3:

score: 0
Accepted
time: 11ms
memory: 7700kb

input:

1413 3
1 3 0 0
3 3 !x 0
2 2 x=0 1
1 2 !y^0 1
2 3 (x^1) 0
3 2 ((!0)) 1
1 1 !!1=(y) 0
2 2 !(1^x)&y 1
3 2 (y)&1|!!1 0
3 1 !x=(y&y=y) 0
2 1 (((!1)^!x)) 1
2 3 !0=(0&y)=1&y 0
1 2 ((((!0)))|!1) 0
3 1 !(y=!1=x|(!x)) 0
1 1 ((((y=!y)))&!0) 0
2 3 ((y=1)^!1^!!1|0) 1
2 3 1|(!x)&!x|1|(x=1) 1
2 3 !0^!!!!y&0=(!1&!0...

output:

4 16 0

result:

ok single line: '4 16 0'

Test #4:

score: 0
Accepted
time: 42ms
memory: 11756kb

input:

181737 10
5 2 1 1
1 10 !1=!x 0
10 1 (1^x) 0
2 4 !1 1
10 8 y=(!1)^1 1
6 2 !((x&!x)) 1
1 10 !!((!x)|x) 1
7 10 (((0))) 0
7 3 !(1)^!x 0
10 4 (!1)&x 0
7 7 !y&!0 1
8 8 !1=(x)|1^1 1
2 6 ((!!!x)) 0
7 2 1 1
2 2 y=1=0 0
6 3 (!0) 0
6 4 0 0
1 1 (!1) 1
1 8 y 1
3 5 !x|!x^!1 0
4 7 (!0) 0
3 4 !1&1&!1|!0 1
2 7 ((0|1...

output:

1024 1048576 0

result:

ok single line: '1024 1048576 0'

Test #5:

score: 0
Accepted
time: 3ms
memory: 8232kb

input:

1 3
1 1 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!...

output:

4 16 0

result:

ok single line: '4 16 0'

Test #6:

score: 0
Accepted
time: 1ms
memory: 9700kb

input:

1 1
1 1 x^y|1 0
1

output:

1 1 0

result:

ok single line: '1 1 0'

Test #7:

score: 0
Accepted
time: 1ms
memory: 7952kb

input:

1 1
1 1 x&y|1 0
1

output:

0 0 0

result:

ok single line: '0 0 0'

Test #8:

score: 0
Accepted
time: 1ms
memory: 7660kb

input:

1 1
1 1 x=y|1 0
1

output:

0 0 0

result:

ok single line: '0 0 0'

Test #9:

score: 0
Accepted
time: 0ms
memory: 7736kb

input:

2 2
1 2 !x&!y 1
1 1 !x&y 0
1

output:

4 12 2

result:

ok single line: '4 12 2'

Test #10:

score: 0
Accepted
time: 49ms
memory: 10912kb

input:

2 10
9 8 ((((!((!x=1))^(!1&(x|x|!y))&((!y&!x=(x=y)))&!((((x=1))&(0=(y))^(!!(!!x^1=x)&(x)^y&1=!x&1=(((!0^(1)^1))^!(((((y))|x|!y))))^!!0=!y&(0)|(y=x&!y&y=x)))=((((!!y&!!0|!0^!0)=!x))))^0&(((!1=!(!x)))|(((((x=1|!y|y)=(!1^1^0^(0)))=!0^1)))=(!(!1^(((((!1)^!x^0))))=(1)^((((y=((x))|(0)|(!1^1)))|(!!!y))=((!...

output:

0 0 0

result:

ok single line: '0 0 0'

Test #11:

score: 0
Accepted
time: 1ms
memory: 7760kb

input:

4 3
1 1 !!!!!!x 0
2 1 !!y 1
1 2 !!!!!x 1
2 2 !!!x 0
1

output:

4 16 0

result:

ok single line: '4 16 0'

Test #12:

score: 0
Accepted
time: 5ms
memory: 22072kb

input:

1 1
1 1 ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

1 1 0

result:

ok single line: '1 1 0'

Test #13:

score: 0
Accepted
time: 46ms
memory: 11828kb

input:

200000 10
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10 !x^!y 1
3 10...

output:

512 262144 134217728

result:

ok single line: '512 262144 134217728'

Test #14:

score: 0
Accepted
time: 1ms
memory: 7636kb

input:

10 3
3 1 (!x) 1
3 2 !1&x&1&!y 1
2 1 ((x)&y) 1
1 3 0 0
2 2 !1&0=y&0 1
3 3 (!y)^y 1
2 1 0|((!y)) 0
3 2 x 0
2 2 (y|1^x) 0
2 1 ((!0)|y) 0
1

output:

8 64 0

result:

ok single line: '8 64 0'

Test #15:

score: 0
Accepted
time: 0ms
memory: 5688kb

input:

0 3
1

output:

8 64 0

result:

ok single line: '8 64 0'