QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#153036 | #6680. Heap | qzzyq | WA | 73ms | 4960kb | C++14 | 1.9kb | 2023-08-29 09:39:32 | 2023-08-29 09:39:32 |
Judging History
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'