QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#325580 | #8226. 堆操作练习题2 | zhouhuanyi | 10 | 5ms | 5904kb | C++14 | 1.4kb | 2024-02-11 17:24:58 | 2024-02-11 17:24:58 |
Judging History
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%