Codeforces Round #713 (Div. 3) A-B Palindrome

​​傳送門​​

C. A-B Palindrome      

You are given a string s consisting of the characters ‘0’, ‘1’, and ‘?’. You need to replace all the characters with ‘?’ in the string s by ‘0’ or ‘1’ so that the string becomes a palindrome and has exactly a characters ‘0’ and exactly b characters ‘1’. Note that each of the characters ‘?’ is replaced independently from the others.

A string t of length n is called a palindrome if the equality t[i]=t[n−i+1] is true for all i (1≤i≤n).

For example, if s=“01???0”, a=4 and b=4, then you can replace the characters ‘?’ in the following ways:

“01011010”;

“01100110”.

For the given string s and the numbers a and b, replace all the characters with ‘?’ in the string s by ‘0’ or ‘1’ so that the string becomes a palindrome and has exactly a characters ‘0’ and exactly b characters ‘1’.

Input

The first line contains a single integer t (1≤t≤104). Then t test cases follow.

The first line of each test case contains two integers a and b (0≤a,b≤2⋅105, a+b≥1).

The second line of each test case contains the string s of length a+b, consisting of the characters ‘0’, ‘1’, and ‘?’.

It is guaranteed that the sum of the string lengths of s over all test cases does not exceed 2⋅105.

Output

#include<bits/stdc++.h>
using namespace std;
char s[400010];

int main()
{
  int t;
  cin>>t;
  while(t--)
  {
//    printf("((((()))))\n");
    int a,b;
    cin>>a>>b;
    scanf("%s",s+1);
    int n = strlen(s+1);
    int flag = 0;
    for(int i = 1; i <= n; i++)
    {
      if(s[i] == '1')
      {
        if(s[n-i+1] == '?')
        {
          s[n-i+1] = s[i];
        }
      }
      else if(s[i] == '0')
      {
        if(s[n-i+1] == '?')
        {
          s[n-i+1] = s[i];
        }
      }
      if(s[i] != '?' && s[n-i+1] != '?')
      {
        if(s[i] != s[n-i+1])
        {
          flag = 1;
        }
      }
    }
    for(int i = 1; i <= n; i++)
    {
      if(s[i] == '0')
      {
        a--;
      }
      else if(s[i] == '1')
      {
        b--;
      }
    }
//    printf("(%s)\n",s+1);
    if(flag || a < 0 || b < 0)
    {
      printf("-1\n");
      continue;
    }
    if((a+b)%2)
    {
      int k = n/2+1;
      if(s[k] == '?')
      if(a % 2)
      {
        s[k] = '0';
        a--;
      }
      else if(b % 2)
      {
        s[k] = '1';
        b--;
      }
      else
      {
        printf("-1\n");
        continue;
      }
      for(int i = 1; i <= n; i++)
      {
        if(s[i] == '?')
        {
          if(a)
          {
            a-=2;
            s[i] = '0';
            s[n-i+1] = '0';
          }
          else if(b)
          {
            b-=2;
            s[i] = '1';
            s[n-i+1] = '1';
          }
        }
      }
    }
    else
    {
      if(a % 2 || b % 2)
      {
        printf("-1\n");
        continue;
      }
      for(int i = 1; i <= n; i++)
      {
        if(s[i] == '?')
        {
          if(a)
          {
            s[i] = '0';
            s[n-i+1] = '0';
            a-=2;
          }
          else if(b)
          {
            s[i] = '1';
            s[n-i+1] = '1';
            b-=2;
          }
        }
      }
    }
    for(int i = 1; i <= n; i++)
    {
      if(s[i] != s[n-i+1])
      {
        flag = 0;
        break;
      }
      else
      {
        flag = 1;
      }
    }
    if(a || b || !flag)
    {
      printf("-1\n");
      continue;
    }
    else
    {
      printf("%s",s+1);
    }
    cout<<endl;
  }
}