QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#153036#6680. HeapqzzyqWA 73ms4960kbC++141.9kb2023-08-29 09:39:322023-08-29 09:39:32

Judging History

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

  • [2023-08-29 09:39:32]
  • 评测
  • 测评结果:WA
  • 用时:73ms
  • 内存:4960kb
  • [2023-08-29 09:39:32]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 100005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
inline int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,a[maxn],b[maxn],Ans[maxn],id[maxn],tot;
void solve(void) {
	int i,j;
	read(n);
	for (i=1;i<=n;i++) read(a[i]);
	for (i=1;i<=n;i++) read(b[i]);
	for (i=n;i>=1;i--) {
		if (a[i]==b[i]) {
			if (i==1||a[i]==b[i/2]) Ans[i]=0;
			else if (a[i]>b[i/2]) Ans[i]=1;
			else Ans[i]=0;
		}
		else {
			int now=i/2;
			int fl=(a[i]>b[i]);
//			gdb(i,a[i],b[i],fl);
			id[tot=1]=i;
			while (now) {
				id[++tot]=now;
				if (b[now]==a[i]) break;
				now/=2;
			}
//			gdb(i,now);
			if (!now) return puts("Impossible"),void();
			if (now>1&&(a[i]>b[now/2])==fl) return puts("Impossible"),void();
			for (j=1;j<tot;j++) if ((a[i]>b[id[j]])!=fl) return puts("Impossible"),void();
			Ans[i]=fl;
			for (j=tot-1;j>=1;j--) swap(b[id[j+1]],b[id[j]]);
		}
	}
	for (i=1;i<=n;i++) printf("%d",Ans[i]);put();
}
signed main(void){
	int T;
	read(T);
	while (T--) solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 73ms
memory: 4960kb

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:

01110011010101000110111010100101100100011111111100011110011001111001101011100
001001100010111
01011010110010110000111111011101100101010001011110100111
0
Impossible
00
010001110001001100111110000011010011101010101111100110011110011010
Impossible
Impossible
010011011
0010001001101000110010110000100100...

result:

wrong answer 1st lines differ - expected: '000101111110101000001010001010...0101001001001000001100111100010', found: '011100110101010001101110101001...1100011110011001111001101011100'