1626 - Brackets sequence

[Farsan]

I thought it was an adhoc but getting WA.Where is the problem?

Code: Select all

//#include <bits/stdc++.h>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include<limits>
#include<iomanip>
#define inf 10000000
#define Max(v) *max_element(v.begin(),v.end())
#define Min(v) *min_element(v.begin(),v.end())
#define inp1(x) scanf("%d",&x)
#define inp2(x,y) scanf("%d %d",&x,&y)
#define Unique(v) v.resize(unique(v.begin(),v.end())-v.begin())
#define Sort(v) sort(v.begin(),v.end(),greater<int>());
#define fread() freopen("inp.txt","r",stdin)
#define fwrite() freopen("out.txt","w",stdout)
#define mem(n,m) memset(n,m,sizeof n)
int Set(int N,int pos){return N=N | (1<<pos);}
int reset(int N,int pos){return N= N & ~(1<<pos);}
bool check(int N,int pos){return (bool)(N & (1<<pos));}
int cnt_leading_zero_bits(int N){return __builtin_clz(N);}
int cnt_trailing_zero_bits(int N){return __builtin_ctz(N);}
int cnt_no_of_bits_on(int N){return __builtin_popcount(N);}
int mod_of_negative_number(int n,int m){return ((n%m)+m)%m;}
//catalan(n+1)=(2*(2*n+1)*catalan(n))/(n+2) ... catalan(0)=1
//priority_queue< int, vector<int>, greater<int> > PQ;// keeps in ascending order
// bool operator < ( const node& b ) const


using namespace std;
int main()
{
    int i,j,k,m,n,t;
    string s,s2;
    inp1(t);
    getchar();
    while(t--)
    {
        getline(cin,s);
        getline(cin,s);
        s2=s;
        for(i=0;i<s.size();i++)
        {
            if(s[i]=='(')
            {
                for(k=s.size()-1;k>i;k--)
                {
                    if(s[k]==')')
                    {
                        s[k]='-';
                        s[i]='-';
                        break;
                    }

                }
            }
           else if(s[i]=='[')
           {
                for(k=s.size()-1;k>i;k--)
                {
                    if(s[k]==']')
                    {
                        s[k]='-';
                        s[i]='-';
                        break;
                    }
                }
            }
        }
        for(i=0;i<s.size();i++)
        {
            if(s[i]=='-')
            cout<<s2[i];
            else if(s[i]=='('||s[i]==')')
            {
                cout<<"()";
            }
            else if(s[i]='['||s[i]==']')
                cout<<"[]";
        }
        cout<<endl;
        if(t)
            cout<<endl;
    }
    return 0;
}

[brianfry713]

Random input:

Code: Select all

100

[)[(]]][)]]]([)(]][[[)([())])[[]](][]])([(][[)[[()([[((])[[[(()]()[](]([]]()([])]]][(())[]([]))]

][[[[()[(][][][[]([])])(]]])([]()[[][()]]([)](][)))[)[]()[)[))[[]())(](]][)[]()([[[]))][()()[[]

]([]]]][)()(([([(]))()(([()(](

[)])([(](((()[)][()(([()(([(]]))((](]]]](]]))(((()()]([]((

(]()])((((]](][)(])(

](([([[)]))[[[[]][]])[]((()]

)]([]][[)])[(](])][][))(())([()(][[])()[([

())]]()[][]][)([])(]([)]][()[[)[([[]]])[[))([[])]])])[]((])[[

)[)])([[[(]])))(](]((([](][))(][[()](([[()[)]])[(([(((](])))[)]())([)[()][][[(([)[[)])[

[]]((])[()()]([[])))[)]]()(][[)([))[([((]()[)](()))]]([])[[])]]](()([[()[)]])(]

)()((]])))([)())(][])[(]((])([])]([

]))(])](

()[]])([)([)]]))[]([)()[)))[()()][([])(()[[()])][[)][[[](])()))(][

[]]]())(]()[]]([)[(([([])]()][]))[()())][]))[)](((([([))[[[)()[[(]](()][((][[][[]](])[(]([(

]][][[][][)]]())](][]])())()]([]]([)[

()()(])[()[]])]))([)[[[())(]]])]([()))][[))[[(]

)))]]]]((](][)[]][()(]][

(([)])[)[)()()[]))[[()[[)][([)([)[])])[[[[][])[(](]])))[(([[)[([((]])))(()[][

()(]()([]([)[]][)][)]([(([)[[(][)])[))(()[[])))[)(](([((([[[[)(])))[[)[]]

[([(]]([]((]())[]]((]))(]([)])[[[([)][][[()[)](([(())[[([([))(]]()(]]

))([]))()(([)[(][[](])(]((()]()())])[()]())[]))[])[][][[][]][(]()[)]][]]]()][]))(]([[[([)()](

][]()[[()[)])][[([))((]([((]()]]][((([)[([)))]])))[))[)][[[[])[[([[((][))][[[[(]][((([]](

)][])[)]][])]())]]]]][)][[))))[[()[)]])[)(((()[]()[]((][[((][[)[]](]])

())))[])](][(])])[](()[[))[((]))(][[))

()[][[()][(([)[)[]][(]()]]])((())](])(((](()[[[([[][)]]([[[[[[]])]][(]]](]([

][())[[()[[]())]((((]](][]])])]

]]]))))

(()()[])]()[])))(([()[[))[[]]])]]](()][(]]][)(]))[)[((]

[)())[

()))[(]]([[[][[)]([[([))(][[((]()()](([(](][])][)[()([[))(])([

)[])[]]][([)]]()([[)](]()(][()][][])[[(([[)))[])()[])[][[[([]]([[](([(((][[(()

([((][])([)])(]([]([)(])])]()([)[[))))[)]]((((([]()

)()())([)[]()))[[(])]()]([[][]]]]((()([]])]([([((

)()]])))(](]]](]])])([]][)(([([](][()]))][)[))))[(

]])[)][[)]((]]]]([)[)]]]((()[)()()()([]))][)])(]])))((()()[][[([((](]][

[()))[)(][)(][)]]][)[]][][[[)(]((())[[[[)][()]]([[)()

[(])]()[([[[])()]))))[()][](]())(([](())[(]))]]()()[[)])][[[[](]][[][((((

[)]))()[[]][)[(])][)[)](([()[((()])[][([[](][([]](())][))[[(]](([[][(]([]())(]((]()(]][)[())]))[

((((([]((((]((]([]]))(][)()][][[][[]))]))(()(])[])(()][](([[]((]]][(([)[[)][)))([)(](][(]([[)])(

(([[)(([([])]]](([)]))[)(([][[)[[](

(([([))[)([)[](])[))[](([)[(([((

[()])]()))())][](][(][[()[(][)[()](][((][((]([]())((][(())(][[(])([](][[]][]))(][(])]([

)[]](

[)])((([[])(]])][]]))[)][[)[)))([))[))(]([(]))[])[([([)]([)[][[)

]]((

(()(([)[)[([()()((])[[](]]][]][](]]([)[]]])(())([))(]()]]()](][(

[()][([)[[)]()))[[(]]][]))]((]][]()[)]]][)[[[(])

]()][((((((]([](]))[((()][(])))))[(][(][(][()))([[][]]([[()])[(

(()[()))(])[([[[))(

)([](][))]])])]([()[][(])])[([[)[((]]](([()))()])[)()[([))()][][[]))[))()[[[[])][](])()[)

])][])[([()])])])][]]([]]]]()()()(]())(])[[[)])[]()[(])([((]([([[][((]]))[

[))(()[[[)][(][]((][][(][

[(((([[)][])))[(][()[([)[)([([[[[[][

)((]])((])][)(()[)]]))](][[[))][)])(([(]]])(]))[]()())()]]](([[))]))))((([(]]))[)]]](](][]][))][((

[)][))]))([][)[))[)(((]])([])][]

))[](]())]]][((())()(][)[)[)]))([]]][]((]]])]])(())))][](((])

]])][][[]))[[([]([))][())())][

][][(](

[[()()]()))])]][((()][][(]()[)((]()])(]][([]]))]))()((](]()))))(

]]]]][)]((][[[]]](]](([()])]())]((]]](]])[)]()[])[[)[()]][[(]]](([]]][[(((]

))([]]()]))](]]]][]])][()(([(]])(](([()[)[))[())[((]][])[]]][[(])(]((([[]]])]([))[)(((

[(

)

[[)([((])[)()()()])[)[[)](]]())]]]])]](())([[)[](]))[][)][((])][([]()((

))(][[[])](]]]([)([([)[[])[()][]([[[())[([)])[[[[([([(])))[](([(](]])()[[])])])

(]([]]])()()[[))[((()[[])]][]()]())]((()[([(

]))()))]](([][)(((())][[(](()(]()(([))[([[[))())()[[)(()]()((())()])])))(([

(([()([[)[]([))[)[][]]][()]()[))[])](([)[)))[[]((][([)[[[[]]((([([)([]

()[)]))])())[](()[])[()((])()))[[]])(()[([][)]]])[(][)][))[[[]((]()]([

)))][([)[)))]])[([([((](]])[]((())(])[)]][)])[))()(()](([)]))][[([[)(])()[]](((()(

]](]))[]]))))]]]][(]([[][[][(([]]

[)])([[)(((]]][]][)))](()((]]()))([)])[])[[()(]

[([]][(([(])(([)()[][([][

]()[(([[])(])[((](([[(](())[(]]]]))()][((]())())()][)[

)]((]]][](]])[)[[([][[(][)[)[(((](([]]([(])))]]]

)[)][([][])[

))])][)]))[[[])[[)]([][])))(](]()[[)(]()(]([[)()[())]((())(()])])]()

(][]]([()]])(((((([

([]]][([[)([([[]](((]])]])(])[()(](()([])][[)()(()(]()[][[[](]()[()((]][[)(())()])

][]])))([()]])(][][([(([))[](]]([[]]((][)

)([)](()([)((])][[[)[(()]()][[]][)())(])]()]]][)))]])]()])()(]([)(([(](]])]]()()[](([())[)[[([()[

(]]([]))[[][])[()(([[[](((])))))())](]([)](()[([])))]()((()[[

][]))]([)))[)[([)]]

([[[[][

)([(]))())[[[((([)[]()))](][]))([]())[)[](([()[[[([[)]](][[[(([[

]]()([((][(((][()()(([([([[()(((]()(])([()[((())

[)(()

)()))[)))[[))][]]])(]))()])[(]))][[((()[[]]][)[[(][](]])[)][((]]][]][()(])])[)]]()[(([)]

))]))[(])())))([())))()[[)]([[]]][)(()]))([])[))([[)[]])([)]()[(]]((

()[(()[[]][)[]()])[)[)

]][]][]([([](()]]()([)((()[)(]]

[)[)())[[()[([)]]]])(()()]))[)))[][[)()]([)()]]([[)[[][([]))([[]

()]

[[()]([[][([][([(()([[(((][()))]])(][[))(

]((

[)(])[))])))[[]])[([)[(]())]))]][(]][())[[](([])(]][[()[)[)[]))[)

)])[)]((]([[[[))(])))[]](]([))[[(]))[)))[]]([))[(]([)])[[)(][[[[[]((()[[)

[][()]]))(

[[]][])))]](]]())][]))))[((()))]]([[]]](][([))]]()[)[]])(]

)([)([][[])[[]]((((]()

AC output:

Code: Select all

[()[()]][][()][][]()[()()][][[[()([()()])[[]]()][]]()([()][][])[[()([][()()])[[[()()]()[]()]()[]]()([])]]][(())[]([])()]

[][][][[()[([][][][[]([])])()]]]()([]()[[][()]]([()]([][])))[]()[]()[()[()()[[]()()()]()]][()[]()([][][])()][]()()[][]

[]([][][][][])()()([]([()]))()()()[()()]()

[()]()()[()]()()()()[()][()(([()()()[()]]))()()]([][][][]([][]))()()()()()[]()[]()()

([]()[])()()()()[][]([][])([])()

[](([([][])]))[[[[]][]]()[]()()()]

()[]([][][[()]()[()]([])][][])()(())([()()][][])()[]()[]

()()[][]()[][][][]()([])([]([()][][]()[][])[([[]][])[[()()([][])]]()])[]()([])[][]

()[()]()()[][[([][])()()()]()]()(([]([][]))([][[()](([][()[()]])[](([()()()]([])))[])]())([])[()][][][(([])[][])])[]

[][](([])[()()]([][]))()[()][]()()[][[()([])()[([()()]()[()](()))]]([])[[]()]][]()()()[[()[()]]()()]

()()(([][]))()()[()()()([][])[()]()([])([])]()[]

[]()()([])[]()

()[][]()([])([()][])()[]([])()[]()()()[()()][([])(()[][()])][][()][][[]([])()()()()][]

[][][]()()([]()[][]([])[](([([])]()[][]))[()()()][])()[()]()()(([]([]))[][][])()[[()]](()[][()()][[][[]]()])[()]()[]()

[][][][[][][()]]()()[]([][][])()()()[]()[][]([])[]

()()([])[()[]]()[]()()([()[[[()()()]]]()]([()()()][][]))[][()]

()()()[][][][]()()[]()[][()[]][()()][][]

(([()])[])[]()()()[]()()[][]()[][()][]([])([()[]()])[][[[][]()[()]()]]()()()[]()([][])[]([](([][])))()()[][]

()([]()([]([()[]][()][()]([(([])[][()][])])[]))(()[][]))()[]()([](([()()([][][][])()])))[][()[]]

[()[()]]()[]()([]())[][](([]))()[]([()])[][][([])][][][()[()]()()[(())[[([]([]))()]]()()]]

()()([])()()(([()[()][[]([])([]((()[]()())[])[()]())[]()()[]()[][][[][]][()]()[()]][]][]()[][]))()[]()[][][([])()]()

[][]()[][()[()]()][][]([])()(([]([](([]()[][][][((([])[]([])))][])))[]))[()][][][][]()[][]()[][(([][]))][][][[()]][()()()[]]()

()[][]()[()][][]()[]()()[][][][][][()][][]()()()()[][()[()]]()[]()()()()()[]()[]()([][[()()][[()[]]()]])

()()()()[]()[]([][([])])[](()[][])()[](([]))([][][])()

()[][[()][(([])[])[]][([]()[][][])()(())]([])()()()]()()[[[([][][])]]()[[[[[[]]()]][()]]]()]()[]

[][()()[[()[[]()()]()()()()]]([][][])]()[]

[][][]()()()()

(()()[])[]()[]()()()(([()[[()()[[]]]()]][](()[][()][][][])([]))[])[()()]

[]()()()[]

()()()[()][]([][[][[()]([][]([]))()][[()()]()()](([()]([][])[][])[]()([][]))()])()[]

()[]()[][][][]([()][]()([[()]()]()([][()][][])[][](([][])))[])()[]()[][][][()[]]()[][]()()[()()()][][]()()

()[(([][])([()])([]([]([()([])])[]()([])[][])))()[()]]()()()()()[]()

()()()()()[()[]()()()[[([])]()]()[[][]]][]()()()([][])[]()[]()[]()()

()()[][]()()()([]([][][]([][])[])([][][])(([([]([][()]))][])[]))()()[]()

[][]()[()][][()](([][][][]([()[()]][]((()[])()()()([]))[][()])([][])))()()()()[][[()[()()]()]][]

[()()()[()()][()()][()]][][()[]][][[[()()]((())[][][][])][()]]([][])()

[([])]()[([][[]()()])()()()[()][]([]())(([](())[()]))][]()()[[()]()][][[[]()]][][][]()()()()

[()]()()()[[]][]()[([])][]()[()]()([]()[]((()[])[][()[[]()][()[]](())][]))[[()]]()()[[][()]([]())()](([]()([][][])[()()]))[]

()()()()()[]()()(([](([]([][]))([][()()][][][][][]))[]))(()([])[])(()[][](([[]()()][][][(([])[][])][])))()[()()]()[][()]([][()])()

()([[()()()[([])]]](([()]))[])()([][][])[][]()

(([]([]))[])([])[]([])[]()()[]()([])[]()()[]()()

[()]()[]()()()()()[][]()[][()][][()[()][()[()]()][()()][()()]([]())()()][(())()][][([])([]([][[]][]))()][([])]()[]

()[][]()

[()]()((([[]()([][])][][]))[()][][])[]()()()([])()[]()()([]([()]))[]()[]([([])]([])[][][])

[][]()()

()()()()[()[()[([()()()()])[[]()]]][]][]([][]([()[]][])(())([]))()[]()[][]()[]()[][]()

[()][([])[[()]()()()[[()]]][]()()](([][][]()[()][][][])[][][()])

[]()[][]()((((([]([]([]))[]((()[][()])))))[()][()][()][]()))()[[][]]([][()])[]()

(()[]())()([])[]([][][])()()

()([]([][()()][])[])[]([]()[][([])])[]([[()[()()]]](([()()()()])[])()[([])()()][][][])()[]()()()[][][[]()][]([])()[]()

[]()[][]()[([()])]()[]()[][][]([][][][]()()()([]())([])[][][()])[]()[]([])()[()()]([]([[][()()]]))[]

[]()()()()[][[()][()][]()()][][()][]

[](((([][()][])))[()][]()[]([])[])()[]()[][][][][][]

()()([][])(([])[][()(()[()][])()]([][[[()()][()]()(([()][][])([]))[]()()()()]][](([][()()]))))()(([()][]))[()][][]([]([][][][]))[][]()()

[()][()()]()()()[][()[()()[()()()()]]()([])][]

()()[]([]())[][][][((())()([][()[()[()]()()()[]]][](([][][])[][])(())))][]()()([])

[][]()[][][][]()()[][([]([]))][()()()()][]

[][][()]()

[[()()]()()()]()[][][]((()[][][()]()[()(([]()[])([][][()[]]))]))()(([]([]())))()()

[][][][][][()]()()[][[[]]]()[][](([()])[]())[]()([][][]([][])[()]()[])[[()[()]][[()]]]()()[][][][][()()()]

()()([][]()[])()[]([][][][][][])[][()(([()][])([](([]()[])[]))[()()[()()]][])[]][][][([])()]((([[]][])[]([]))[])()()()

[]()

()

[[()([(([])[()()()()])[()[[()]([][]())]]][])]](())([][])[]([])()[][()][()([])][]()[]()()()

()()([][[[]()]()][][]([])([]([])[][])[()][]([][][]())[([])])[][][][]([]([()]))()[]()([([]([][])()[[]()])])

([]([][][])()()[[()()[()(()[][])]][]()]())[]()()()[]()[]()

[]()()()()()[][](([][])(((())[][][()](()([]()(([]))[]([][][]))())()[[()()()]()((())()[])])))()()[]

(([()([][])[]([])()[()[][]]][()]()[()()[]()](([])[])))[[]()()][]([])[][][[]]()()()[]([])()[]

()[()]()()[]()()()[](()[])[]()(([])())()[[]]()(()[([][])][][])[]([][()][])()[[[]()()]()]()[]

()()()[][]([()[()()()]])[([()[(([]([][])[]((())([])[()][][()])[]))()()()](([()]))][][([][])()])()[]]()()()()()

[][]([])()[][]()()()()[][][][][()]()[][][][][()()[]]

[()]()()[][()((([][][][][][])))](()(([][]()))([()])[])[][()()]

[()[]][]()([()])()([])()[][]()[][]

[]()[]()([[]()([])[()()](([[()](())[()]][][]))()][(([]())())()][])[]

()[]()([][][][]([][])[])[[([][][()][])[()[()()()](([][]([()])))]]]

()[()][]([][])[]

()()[]()[][()]()()[[[]()[[()]([][])()()()]()]()[[()()]()()]([][])()[()()]((())(()[])[])]()

()[][][]([()][])()()()()()()[]

([][][][([[()([()[[]]()()()][])]])()])[()()](()([])[][][])()()()([]()[][[[]()]()[()()()]][][()(())()])

[][][]()()()([()][])()[][][()[(([]))[]()]]()[[]]()([][])

()()[()]()()([()(([])[][[[()[()()]()][[]][()()()([])]()]][][()()()][])]()[])()()[]()[()()()[()]([][])][]()()[](([]())[])[][]()[]()[]

([][]([]))[[][]()[()(([][][]((([])))))()()]()]([()](()[]([])))[]()()()()[][]

[][]()()[]([])()()[()[([])]]

()[][][][][]

()([()])()()()[][][((([])[]()))]([][])()([]())[]()[]()()[]()[[[([][])]]()][][][]()()[][]

[][]()()[()()][()()()][]()()()()[]()[]([[()()()()]()()])()[]()[]()(())

[]()()()

()()()()[()()()[[()()][]]]()([])()()[]()[([])()][[((()[[]][][()[[()][]()]])[])][(([][][][][][()([])])[])]]()[()([])]

()()[]()()[]([])()()()()([]())()()()[[()]()[[]]][()(()[])()([])[()()([][()[]])([])]()[()]]()()

()[](()[[]][()[]()])[]()[]()

[][][][][]()[()[]()()][]()()[()()(()[])()][]

[]()[()()()[[()[([])]]]]()(()()[])()[()()()[][[()()]([])()]]([][])[][][]([])()()[][]

()[]

[][()]()[][][]([][]([()()([[()(([][]()))]])()][][]))()

[]()()

[()([])[()()]()()()[[]]()[([])[([]())]()()]][]([][][]())[][](([])([][][][]()[])[])[]()()[]()

()[]()[()](([]([][][[()()([])()()[]]()]([]))[][()]))[()()()[]]([])()[()]([()])[][()()][][][][][]()(()[][])

[][()][]()()()

[[]][]()()()[][]([][]())[][]()()()()[((()))][]()[[]][]()[][([()()][]()[()[]])()]

()()[()([][][])[[]]()()()()]()

Other outputs are acceptable as long as it has the minimal possible length and contains the given sequence as a subsequence.