QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#141228#6680. HeapOvO_ZuoWA 139ms4828kbC++141.1kb2023-08-17 09:50:182023-08-17 09:50:21

Judging History

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

  • [2023-08-17 09:50:21]
  • 评测
  • 测评结果:WA
  • 用时:139ms
  • 内存:4828kb
  • [2023-08-17 09:50:18]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,v[N],a[N],b[N];
int f=0,ff=0;
bool dfs(int x,int vv)
{
	if(!x) return false;
	if(a[x]==vv&&a[x>>1]!=a[x])
	{
		if(x>1&&a[x>>1]<a[x]) f=0;
		else if(x>1&&a[x>>1]>a[x]) f=1;
		return true;
	}
	bool fff=dfs(x>>1,vv);
	if(a[x]<vv) ff=1;
	else if(a[x]>vv) ff=0;
	swap(a[x>>1],a[x]);
	return fff;
}
void sol()
{
	scanf("%d",&n);
	int i,j,x;
	for(i=1;i<=n;i++) scanf("%d",&v[i]);
	for(i=1;i<=n;i++) scanf("%d",&a[i]);
	for(i=n;i>=1;--i)
	{
		f=ff=-1;
		if(!dfs(i,v[i])){
			puts("Impossible");
			return;
		}
		if((f!=-1)&&(ff!=-1)&&(f!=ff)){
			puts("Impossible");
			return;
		}
		if(f==-1) f=ff;
		if(f==-1) f=0;
		b[i]=f;
	}
	for(i=1;i<=n;i++) printf("%d",b[i]);
	puts("");
	return;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t)
	{
		--t;
		sol();
	}
	return 0;
}
/*
从后往前考虑
可以知道当前最后一个点x的运动轨迹,通过判断被交换的点/最终位置父节点和a[x]的大小关系即可
因为每次移动的位置是logn级别的,复杂度 nlogn
*/

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3648kb

input:

3
4
2 3 1 4
4 1 3 2
5
4 5 1 2 3
3 4 1 5 2
3
1 1 2
2 1 1

output:

0101
Impossible
001

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 139ms
memory: 4828kb

input:

1118
77
210555 375330 669075 785279 194474 310626 830710 886719 102133 426324 41900 971872 167203 702222 230534 112350 673156 358623 886831 72864 818751 367894 842740 531878 818794 131219 412128 104469 70427 658494 72060 768735 915294 161365 91671 451974 121863 498890 408674 670274 875754 967228 518...

output:

00010111111010100000101000101001111010010000100101001001001000001100111100010
000001011011010
01011011111111010011000100101100101010000110111000001100
0
Impossible
01
011001000010010011110011010100110010111110101000010001101101000011
Impossible
01010010110111011101000001101111111111000101100111110
0...

result:

wrong answer 9th lines differ - expected: 'Impossible', found: '01010010110111011101000001101111111111000101100111110'