題目鏈接：CF1153C

題目大意

給你一個(gè)串刷晋，只包含字符 "(" ")" "?",問(wèn)可不可以通過(guò)吧 "?" 變成括號(hào)陪蜻，使得字符串s滿足：
1.整個(gè)串是合法的括號(hào)序列
2.任何前綴都不是一個(gè)合法的括號(hào)序列
如果可以輸出轉(zhuǎn)換后的串，否則輸出“:(”

Input

第一個(gè)行輸入一個(gè) 表示字符串長(zhǎng)度
第二行輸入一個(gè)只含有題意中字符的串

Output

如果有解腥刹，輸出這個(gè)解
沒(méi)有則輸出“:(”

樣例

Input:

6
(?????

Output:

(()())

Input:

10
(???(???(?

Output:

:(

解題思路

s[0...t-1] ="(((?))?)"

一個(gè)串整體是合法括號(hào)序列马胧，那么必有s[0]='('和s[t-1]=')'
任意前綴都不是合法序列，那么去掉s的開(kāi)頭和結(jié)尾衔峰，剩下的中間這部分一定是一個(gè)合法括號(hào)序列佩脊。

對(duì)于s,開(kāi)頭結(jié)尾已經(jīng)是"("和")"了蛙粘，剩下部分用區(qū)間[l,r]表示：
s[l...r]=((?))?
需要讓這段區(qū)間是合法序列，我們遍歷這個(gè)區(qū)間威彰，更改"出牧？"，從開(kāi)頭到每一個(gè)位置為止歇盼，左括號(hào)數(shù)量不能小于右括號(hào)的數(shù)量（多出的右括號(hào)會(huì)和s[0]湊成一個(gè)合法前綴）舔痕，最后在這個(gè)區(qū)間中，左括號(hào)數(shù)量等于右括號(hào)數(shù)量的話豹缀，即為答案伯复。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
string s;
int t;
int main(){
    cin>>t;
    cin>>s;
    if(t%2!=0
       ||t==0
       ||s[0]==')'
       ||s[t-1]=='('
       ){//答案一定是偶數(shù)長(zhǎng)度的串，s[0]不是),s[t-1]不是(
            cout<<":("<<endl;
            return 0;
       }
    s[0]='(';
    s[t-1]=')'; //上面判斷后 s[0] s[t-1] 一定可以改成這樣
    int l=1,r=t-2; // 區(qū)間 [l,r]
    int jsl=0,jsr=0,f;
    for(int i=l;i<=r;i++){  //遍歷掃一遍邢笙，統(tǒng)計(jì)左括號(hào)啸如，右括號(hào)已經(jīng)有多少個(gè)
        if(s[i]=='(') jsl++;
        else if(s[i]==')') jsr++;
    }

    int m = (r-l+1)/2; //如果區(qū)間長(zhǎng)度是6，左括號(hào)右括號(hào)肯定不大能于3個(gè)氮惯，m=3;
    f=1; //記錄結(jié)果是否可以
    if(jsl>m||jsr>m)f=0;
    int acl=0,acr=0; //遍歷時(shí)叮雳，記錄已經(jīng)出現(xiàn)多少左括號(hào)和右括號(hào)
    if(f)
    for(int i=l;i<=r;i++){
       if(s[i]=='('){
            acl++; //左括號(hào)用正數(shù)表示
        }else if(s[i]==')'){
            acr--; //右括號(hào)用負(fù)數(shù)表示
            if(acl+acr<0){f=0;break;} //任何時(shí)候，右括號(hào)不能比左括號(hào)出現(xiàn)的多
        }else if(s[i]=='?'){
            if(acl+acr==0){ // 左右括號(hào)相等妇汗，"()"帘不，肯定放"("
                s[i]='(';
                acl++;
                jsl++;
                if(jsl>m){f=0;break;} //不能多于m個(gè)
            }else if(acl+acr<0){ //右括號(hào)不能比左括號(hào)多
                f=0;
                break;
            }else if(acl+acr>0){ //這里"("多，可以放"("或")",優(yōu)先放"(",否則會(huì)錯(cuò)铛纬，比如s[l,r]="((?))?"
                if(jsl+1<=m){
                    s[i]='(';
                    acl++;
                    jsl++;
                }else{
                    s[i]=')';
                    jsr++;
                    acr--;
                    if(jsr>m){f=0;break;}
                }
            }
        }
    }
    if(f)
        if(!(acl+acr==0&&jsl<=m&&jsr<=m&&jsl+jsr==m*2))f=0;
    if(f)cout<<s<<endl;
    else cout<<":("<<endl;
    return 0;
}