Double

Recently, $Jvruo_{}$ became obsessed with a fighting game. In this game, $n_{}$ characters stand on an arena from left to right, and the combat power of the $i_{th}$ character is $a_i$ . For each operation, $Jvruo_{}$ will choose two adjacent characters $x_{}$ and $y_{}$ on the arena for a duel. If $a_x> a_y$ , then $x_{}$ wins, if $a_x <a_y$ , then $y_{}$ wins. If $a_x = a_y$ , then both $x_{}$ and $y_{}$ have a probability of $50\%$ to win. The victorious character will stay in the arena and double the combat power; the losing character will leave the arena.

Now $Jvruo_{}$ will perform $n-1_{}$ operations, after $n-1_{}$ operations, there will only be one character left in the ring. Obviously, $Jvruo_{}$ has $(n-1)!\$ operation modes. In all these modes of operation, which characters have the probability to stay till the end and become the final winner.

The first line contains a positive integer $n(1 \le n \le 5 * 10^5)$ , which represents the number of the characters.

The second line contains $n_{}$ integers separated by spaces $a_i(1 \le a_i \le 10^9)$ , which represents the the combat power of the $i_{th}$ character.

The first line contains a positive integer $m_{}$ , which represents the number of the characters who have the probability to stay till the end and become the final winner.

The second line contains $m_{}$ integers in $ascending_{}$ order separated by spaces $b_i(b_1 < b_2 < …… < b_m)$ , which represents the the index of the characters who have the probability to stay till the end and become the final winner.

#include<bits/stdc++.h> using namespace std; int a[500005],n,b[500005]; bool test(int x){ int k=a[x],y=x+1; x--; while((a[x]<=k||a[y]<=k)&&k<=1e9){ if(a[x]<=k) k<<=1,x--; else if(a[y]<=k) k<<=1,y++; } return k>=1e9||(!x&&y>n); } int main(){ int s=0; cin>>n,a[0]=a[n+1]=2e9+1; for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) if(test(i)) b[++s]=i; cout<<s<<endl; for(int i=1;i<=s;i++) printf("%d ",b[i]); }

详情