## 1626 - Brackets sequence

Moderator: Board moderators

Farsan
New poster
Posts: 34
Joined: Fri Aug 12, 2011 6:37 am

### Re: 1626 - Brackets sequence

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 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_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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 1626 - Brackets sequence

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.
Check input and AC output for thousands of problems on uDebug!