Abhishek

E.Double or Append


#include <stdio.h>
#include <stdint.h>

int main(){
int T;
if(scanf("%d",&T)!=1) return 0;
while(T--){
int M;
scanf("%d",&M);
unsigned long long inv = 0;
unsigned long long S = 1; // length of A
unsigned long long P = 0; // sum f[v]*pref[v]
int mex = 1;

for(int i = 0; i < M; i++){
int t;
scanf("%d",&t);
if(t == 1){
// prepend mex
inv += S;
P += S;
S += 1;
mex += 1;
} else {
// double
inv = inv * 2 + P;
P = P * 4;
S = S * 2;
}
printf("%llu", inv);
if(i+1 < M) putchar(' ');
}
putchar('\n');
}
return 0;
}

6 days ago | [YT] | 1