C. A-B Palindrome Solution | CodeForces Round 713 Div. 3

 C. A-B Palindrome

time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

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

For example, if ="01?????0", =4 and =4, then you can replace the characters '?' in the following ways:

  • "01011010";
  • "01100110".

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

Input

The first line contains a single integer  (1104). Then  test cases follow.

The first line of each test case contains two integers  and  (0,2105+1).

The second line of each test case contains the string  of length +, consisting of the characters '0', '1', and '?'.

It is guaranteed that the sum of the string lengths of  over all test cases does not exceed 2105.

Output

For each test case, output:

  • "-1", if you can't replace all the characters '?' in the string  by '0' or '1' so that the string becomes a palindrome and that it contains exactly  characters '0' and exactly  characters '1';
  • the string that is obtained as a result of the replacement, otherwise.

If there are several suitable ways to replace characters, you can output any.

Example
input
Copy
9
4 4
01?????0
3 3
??????
1 0
?
2 2
0101
2 2
01?0
0 1
0
0 3
1?1
2 2
?00?
4 3
??010?0
output
Copy
01011010
-1
0
-1
0110
-1
111
1001
0101010
Solution:


#include <bits/stdc++.h>

using namespace std;

#define int            long long int
#define F              first
#define S              second
#define pb             push_back
#define si             set <int>
#define vi             vector <int>
#define pii            pair <int, int>
#define vpi            vector <pii>
#define vpp            vector <pair<int, pii>>
#define mii            map <int, int>
#define mpi            map <pii, int>
#define spi            set <pii>
#define endl           "\n"
#define sz(x)          ((int) x.size())
#define all(p)         p.begin(), p.end()
#define double         long double
#define que_max        priority_queue <int>
#define que_min        priority_queue <int, vi, greater<int>>
#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)       for(auto x : a) cout << x << " "; cout << endl
#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl
#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl

inline int power(int a, int b)
{
  int x = 1;
  while (b)
  {
    if (b & 1) x *= a;
    a *= a;
    b >>= 1;
  }
  return x;
}

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
  const char* comma = strchr (names + 1, ',');
  cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

const int N = 200005;

void solve() {
// take input
int a,b;
cin>>a>>b;

string s;
cin>>s;

int x=a,y=b;
// decrease count of current 0 and 1 from a and b
a-=count(s.begin(),s.end(),'0'),b-=count(s.begin(),s.end(),'1');

for(int i=0,j=s.length()-1; i<=j; i++,j--){
  //if s is of odd length and in the middle there's ?
  if(i==j && s[i]=='?'){
    if(x%2){
      s[i]='0';
      a--;
    }
    else if(y%2){
      s[i]='1';
      b--;
    }
  }
  // if both side there's ?
  else if(s[i]=='?' && s[j]=='?')continue;
  // if in the left its ? but not in right
  else if(s[i]=='?'){
    if(s[j]=='0' && a>0){
      a--;
      s[i]='0';
    }
    else if(s[j]=='1' && b>0){
      b--;
      s[i]='1';
    }
  }
  // if in right its ? but not in left
  else if(s[j]=='?'){
    if(s[i]=='0' && a>0){
      a--;
      s[j]='0';
    }
    else if(s[i]=='1' && b>0){
      b--;
      s[j]='1';
    }
  }
}

// if theres odd number of ? then its not possible
if(count(s.begin(),s.end(),'?')%2){
  cout<<-1<<endl;
  return;
}

for(int i=0,j=s.length()-1; i<=j; i++,j--){
  // if both left and right are ?
  if(s[i]=='?'){
    if(a>1){
      a-=2;
      s[i]='0',s[j]='0';
    }
    else if(b>1){
      b-=2;
      s[i]='1',s[j]='1';
    }
    // if a and b are less than 2 then its not possible to replce ?
    else{
      cout<<-1<<endl;
      return;
    }
  }
}

// check for palindrome and a and b are equal to 0
for(int i=0,j=s.length()-1; i<=j; i++,j--)
  if(s[i]!=s[j] || (a!=0 || b!=0)){
    cout<<-1<<endl;
    return;
  }

cout<<s<<endl;

}

int32_t main()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);


  clock_t z = clock();

  int t = 1;
  cin >> t; 
  while (t--) solve();



  return 0;
}

Post a Comment

0 Comments