QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#325580#8226. 堆操作练习题2zhouhuanyi10 5ms5904kbC++141.4kb2024-02-11 17:24:582024-02-11 17:24:58

Judging History

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

  • [2024-05-22 20:40:58]
  • hack成功,自动添加数据
  • (/hack/631)
  • [2024-02-11 17:24:58]
  • 评测
  • 测评结果:10
  • 用时:5ms
  • 内存:5904kb
  • [2024-02-11 17:24:58]
  • 提交

answer

#include<iostream>
#include<cstdio>
#define N 18
using namespace std;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int h,q,ans,tong[1<<N],length,a[1<<N],b[1<<N];
bool used[1<<N],used2[1<<N],vis[1<<N];
void get_flip(int x)
{
	if (x==(1<<h)) return;
	if (!b[x])
	{
		get_flip(x+1);
		return;
	}
	int d=x;
	while (b[d<<1]||b[(d<<1)+1])
	{
		if (b[d<<1]<b[(d<<1)+1]) d=(d<<1)+1;
		else d<<=1;
	}
	if (!vis[d])
	{
		d=x,b[x]=0;
		while (b[d<<1]||b[(d<<1)+1])
		{
			if (b[d<<1]<b[(d<<1)+1]) swap(b[d],b[(d<<1)+1]),d=(d<<1)+1;
			else swap(b[x],b[d<<1]),d<<=1;
		}
		get_flip(x);
	}
	else get_flip(x+1);
	return;
}
int main()
{
	int op,x,y;
	h=read();
	for (int i=1;i<=(1<<h)-1;++i) a[i]=read();
	q=read();
	for (int i=1;i<=q;++i)
	{
		op=read(),x=read(),y=read();
		if (op==1)
		{
			if (y==1) used[x]=1;
			else used2[x]=1;
		}
		else if (op==2)
		{
			if (y==1) used[x]=0;
			else used2[x]=0;
		}
		else
		{
			length=ans=0;
			for (int j=1;j<=(1<<h)-1;++j)
				if (used2[j])
					tong[++length]=j;
			for (int j=0;j<(1<<length);++j)
			{
				for (int k=1;k<=(1<<h)-1;++k) b[k]=a[k],vis[k]=used[k];
				for (int k=1;k<=length;++k)
					if ((j>>(k-1))&1)
						vis[tong[k]]=1;
				get_flip(1),ans+=(b[x]==y);
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}

詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 0ms
memory: 3808kb

input:

2
3 2 1
50
3 3 1
1 1 2
1 2 1
2 2 1
1 2 2
2 1 2
1 1 1
1 3 2
2 1 1
2 2 2
3 1 2
3 1 3
2 3 2
1 3 2
1 2 2
2 2 2
1 2 1
1 1 2
3 1 1
2 1 2
1 1 1
2 1 1
3 1 2
3 1 3
2 3 2
1 3 2
2 2 1
1 2 1
1 1 1
3 1 2
2 1 1
1 1 1
3 3 1
2 1 1
2 3 2
1 3 1
2 3 1
1 1 2
3 1 3
2 1 2
3 3 1
3 1 3
3 1 1
3 1 1
1 3 2
1 1 1
2 1 1
3 1 1
2...

output:

0
1
0
0
0
2
0
1
2
0
1
0
0
0
0

result:

ok 15 numbers

Test #2:

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

input:

2
3 1 2
50
1 2 2
3 3 2
2 2 2
1 3 1
1 1 1
3 3 2
2 1 1
3 1 3
2 3 1
1 3 1
1 1 1
1 2 2
2 1 1
3 1 3
2 3 1
2 2 2
1 1 2
1 2 1
1 3 1
2 1 2
3 3 2
1 1 1
2 3 1
1 3 2
2 3 2
1 3 1
2 2 1
3 3 2
3 1 1
2 3 1
2 1 1
1 3 1
2 3 1
3 1 3
3 1 3
3 1 3
1 1 1
2 1 1
3 1 2
1 2 1
3 1 1
3 3 2
3 1 3
2 2 1
1 1 1
2 1 1
1 2 1
1 1 2
2...

output:

0
1
1
2
1
1
0
0
0
0
0
0
0
0
0

result:

ok 15 numbers

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #3:

score: 0
Wrong Answer
time: 1ms
memory: 5832kb

input:

4
15 14 13 9 10 11 12 2 7 4 5 1 6 8 3
500
3 1 15
3 1 13
1 9 1
1 6 2
1 15 2
1 14 1
1 10 2
1 5 2
3 12 1
1 1 1
1 4 1
3 6 6
3 10 4
1 3 1
3 13 6
1 11 2
2 4 1
2 14 1
3 6 6
3 1 11
3 1 14
3 2 4
2 6 2
2 15 2
3 1 9
3 7 12
1 13 2
2 9 1
2 5 2
3 14 8
1 15 2
1 12 1
3 11 5
1 5 2
3 1 15
3 5 10
3 1 11
1 14 1
2 13 2
...

output:

0
0
0
0
8
0
0
16
0
0
0
0
0
8
16
16
0
0
0
32
0
0
32
16
0
0
16
0
0
0
0
4
0
0
0
0
8
0
0
0
0
0
64
0
0
128
0
0
0
96
64
256
0
0
64
0
0
0
8
4
2
0
2
0
0
0
0
8
4
16
0
0
2
0
2
8
0
0
16
0
8
0
0
16
32
0
32
0
4
4
0
0
0
0
0
0
4
0
0
0
2
0
0
0
0
0
0
2
0
0
0
16
8
0
0
0
0
8
0
4
0
4
4
4
16
0
8
8
16
16
0
0
8
0
0
0
0
0
...

result:

wrong answer 8th numbers differ - expected: '8', found: '16'

Subtask #3:

score: 0
Wrong Answer

Test #5:

score: 0
Wrong Answer
time: 5ms
memory: 5904kb

input:

9
511 509 510 504 507 505 508 501 503 506 502 494 500 499 493 473 483 495 475 491 497 461 487 490 489 498 496 478 485 480 488 378 469 482 477 462 448 422 470 424 467 421 492 439 454 484 451 376 385 458 464 463 486 411 472 449 474 459 468 479 413 457 455 371 315 432 437 466 453 476 418 433 363 434 38...

output:

0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
1
1
0
1
0
1
1
0
0
0
1
1
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
0
0
1
0
0
0
0
1
0
0
0
1
0
0
0
1
0
0
1
0
0
0
1
0
0
0
0
1
1
0
1
0
0
1
0
0
0
0
1
0
0
1
0
1
0
0
1
0
0
1
0
1
0
0
1
1
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
...

result:

wrong answer 17th numbers differ - expected: '1', found: '0'

Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #3:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%