1512-C, *1200

Problem - 1512C - Codeforces

문제

• 길이가 $n(1\leq n \leq 2 \cdot 10^{5})$이고 0, 1, ? 로만 구성된 문자열 $s$가 주어진다
• s의 ? 를 0과 1로 바꿔서 0과 1이 각각 $a,\ b$개인 Palindrome을 만들 수 있는가?

 

$O(n)$

우선 0과 1이 각각 $a,\ b$개여야 한다는 조건만을 생각하며 문자열을 변형시키자

그 후, 문자열이 Palindrome이고 0과 1이 $a,\ b$개인지 검사한다

#include <bits/stdc++.h>
#define endl "\n"
#define loop(i, n) for(int i = 1; i <= n; i++)
using namespace std;
 
int n, a, b;
char s[200001];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        cin >> a >> b;
        n = a+b;
        cin >> s+1;
        loop(i, n){
            if(s[i] == '?' && s[n+1-i] != '?') s[i] = s[n+1-i];
        }
 
        loop(i, n){
            if(s[i] == '0') a--;
            if(s[i] == '1') b--;
        }
 
        loop(i, n){
            if(a <= 1) break;
            if(s[i] == '?'){
                s[i] = '0';
                s[n+1-i] = '0';
                a -= 2;
            }
        }
 
        loop(i, n){
            if(b <= 1) break;
            if(s[i] == '?'){
                s[i] = '1';
                s[n+1-i] = '1';
                b -= 2;
            }
        }
 
        if(a == 1 && s[(1+n)/2] == '?') s[(1+n)/2] = '0';
        if(b == 1 && s[(1+n)/2] == '?') s[(1+n)/2] = '1';
 
        bool flag = true;
        loop(i, n){
            if(s[i] == '?' || s[i] != s[n+1-i]) flag = false;
        }
        if(a < 0 || b < 0) flag = false;
 
        if(flag){
            loop(i, n) cout << s[i];
            cout << endl;
        }
        else cout << -1 << endl;
 
    }
 
    return 0;
}cs