27207f6482 2016-05-12 kinaba: #include <iostream> 27207f6482 2016-05-12 kinaba: #include <sstream> 27207f6482 2016-05-12 kinaba: #include <iomanip> 27207f6482 2016-05-12 kinaba: #include <vector> 27207f6482 2016-05-12 kinaba: #include <string> 27207f6482 2016-05-12 kinaba: #include <map> 27207f6482 2016-05-12 kinaba: #include <set> 27207f6482 2016-05-12 kinaba: #include <algorithm> 27207f6482 2016-05-12 kinaba: #include <numeric> 27207f6482 2016-05-12 kinaba: #include <iterator> 27207f6482 2016-05-12 kinaba: #include <functional> 27207f6482 2016-05-12 kinaba: #include <complex> 27207f6482 2016-05-12 kinaba: #include <queue> 27207f6482 2016-05-12 kinaba: #include <stack> 27207f6482 2016-05-12 kinaba: #include <cmath> 27207f6482 2016-05-12 kinaba: #include <cassert> 27207f6482 2016-05-12 kinaba: #include <tuple> 27207f6482 2016-05-12 kinaba: using namespace std; 27207f6482 2016-05-12 kinaba: typedef long long LL; 27207f6482 2016-05-12 kinaba: typedef complex<double> CMP; 27207f6482 2016-05-12 kinaba: 27207f6482 2016-05-12 kinaba: class ParenthesesDiv1Easy { public: 27207f6482 2016-05-12 kinaba: vector <int> correct(string s) 27207f6482 2016-05-12 kinaba: { 27207f6482 2016-05-12 kinaba: if(s.length()%2 == 1) 27207f6482 2016-05-12 kinaba: return vector<int>(1, -1); 27207f6482 2016-05-12 kinaba: 27207f6482 2016-05-12 kinaba: vector<int> ans; 27207f6482 2016-05-12 kinaba: 27207f6482 2016-05-12 kinaba: int d = 0; 27207f6482 2016-05-12 kinaba: int peak = 0, peak_i = -1; 27207f6482 2016-05-12 kinaba: for(int i=0; i<s.size(); ++i) { 27207f6482 2016-05-12 kinaba: if(d == 0 && s[i]==')') { 27207f6482 2016-05-12 kinaba: int sec_s = i; 27207f6482 2016-05-12 kinaba: int sec_d = -1; 27207f6482 2016-05-12 kinaba: int bot=-1, bot_k=i; 27207f6482 2016-05-12 kinaba: for(int k=sec_s+1; sec_d<0 && k<s.size(); ++k) { 27207f6482 2016-05-12 kinaba: sec_d += (s[k]=='(' ? +1 : -1); 27207f6482 2016-05-12 kinaba: if(bot>sec_d) { bot=sec_d, bot_k=k; } 27207f6482 2016-05-12 kinaba: } 27207f6482 2016-05-12 kinaba: ans.push_back(sec_s); 27207f6482 2016-05-12 kinaba: ans.push_back(bot_k); 27207f6482 2016-05-12 kinaba: reverse(s.begin()+sec_s, s.begin()+bot_k+1); 27207f6482 2016-05-12 kinaba: for(auto it=s.begin()+sec_s; it!=s.begin()+bot_k+1; ++it) 27207f6482 2016-05-12 kinaba: *it=(*it=='(' ? ')' : '('); 27207f6482 2016-05-12 kinaba: --i; 27207f6482 2016-05-12 kinaba: } else { 27207f6482 2016-05-12 kinaba: d += (s[i]=='(' ? +1 : -1); 27207f6482 2016-05-12 kinaba: if(peak<d) { peak=d; peak_i=i; } 27207f6482 2016-05-12 kinaba: } 27207f6482 2016-05-12 kinaba: } 27207f6482 2016-05-12 kinaba: 27207f6482 2016-05-12 kinaba: int back = d/2; 27207f6482 2016-05-12 kinaba: if(back) { 27207f6482 2016-05-12 kinaba: int p=peak_i, d=peak; 27207f6482 2016-05-12 kinaba: for(;; --p) { 27207f6482 2016-05-12 kinaba: d -= (s[p]=='(' ? +1 : -1); 27207f6482 2016-05-12 kinaba: if(d==peak-back) { 27207f6482 2016-05-12 kinaba: ans.push_back(p); 27207f6482 2016-05-12 kinaba: ans.push_back(peak_i); 27207f6482 2016-05-12 kinaba: break; 27207f6482 2016-05-12 kinaba: } 27207f6482 2016-05-12 kinaba: } 27207f6482 2016-05-12 kinaba: } 27207f6482 2016-05-12 kinaba: 27207f6482 2016-05-12 kinaba: return ans.size()>10 ? vector<int>(1, -1) : ans; 27207f6482 2016-05-12 kinaba: } 27207f6482 2016-05-12 kinaba: }; 27207f6482 2016-05-12 kinaba: 27207f6482 2016-05-12 kinaba: // BEGIN CUT HERE 27207f6482 2016-05-12 kinaba: #include <ctime> 27207f6482 2016-05-12 kinaba: double start_time; string timer() 27207f6482 2016-05-12 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 27207f6482 2016-05-12 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 27207f6482 2016-05-12 kinaba: { os << "{ "; 27207f6482 2016-05-12 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 27207f6482 2016-05-12 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 27207f6482 2016-05-12 kinaba: void verify_case(const vector <int>& Expected, const vector <int>& Received) { 27207f6482 2016-05-12 kinaba: bool ok = (Expected == Received); 27207f6482 2016-05-12 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 27207f6482 2016-05-12 kinaba: cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } 27207f6482 2016-05-12 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 27207f6482 2016-05-12 kinaba: #define END verify_case(_, ParenthesesDiv1Easy().correct(s));} 27207f6482 2016-05-12 kinaba: int main(){ 27207f6482 2016-05-12 kinaba: 27207f6482 2016-05-12 kinaba: CASE(0) 27207f6482 2016-05-12 kinaba: string s = ")("; 27207f6482 2016-05-12 kinaba: int __[] = {0, 0, 1, 1 }; 27207f6482 2016-05-12 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); 27207f6482 2016-05-12 kinaba: END 27207f6482 2016-05-12 kinaba: CASE(1) 27207f6482 2016-05-12 kinaba: string s = "))))))(((((("; 27207f6482 2016-05-12 kinaba: int __[] = {0, 5, 6, 11 }; 27207f6482 2016-05-12 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); 27207f6482 2016-05-12 kinaba: END 27207f6482 2016-05-12 kinaba: CASE(2) 27207f6482 2016-05-12 kinaba: string s = "))()())()"; 27207f6482 2016-05-12 kinaba: int __[] = {-1 }; 27207f6482 2016-05-12 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); 27207f6482 2016-05-12 kinaba: END 27207f6482 2016-05-12 kinaba: CASE(3) 27207f6482 2016-05-12 kinaba: string s = ")()((("; 27207f6482 2016-05-12 kinaba: int __[] = {0, 0, 3, 3, 5, 5 }; 27207f6482 2016-05-12 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); 27207f6482 2016-05-12 kinaba: END 27207f6482 2016-05-12 kinaba: CASE(4) 27207f6482 2016-05-12 kinaba: string s = "()"; 27207f6482 2016-05-12 kinaba: vector <int> _; 27207f6482 2016-05-12 kinaba: END 27207f6482 2016-05-12 kinaba: CASE(5) 27207f6482 2016-05-12 kinaba: string s = "))))()))(((()()((()()))))(())))(()()))))))())))))()()(()()(()))())((()))()((())))()())((()())(()(())))())()(()(()(()))))())))((()((())((()())(()())(()))((()()(()(()))((((((((((())((((()())()(()()())()(((((((()()())(()))(()())))))())((((())()(())(((()((()(())))(()((()())(((((()(()())(((()))()))(((()()()))()())))(())(())(()))))())(()))))()(()(()())(()())((()))()()((())(((()(((()(()()((())())())((()))))())((((())(()()()())(((((())(((())))))())()))()())())))(()()())((((()()))))())())())()())((()))(()(()))()(())))(()))()))(())((()())())())((((())))(()())())))(()((())()()())()))()))())(())((((()()((()(()())()(((()))))(()()()))())))(()())(())())(()))()())((()))((())))()((())(()))))))()(()(((()())(())(()((()((((())))((())))))()))()(()())()())))())(())))((()))()))(()()))())(()(())((()(()))((((()()())())(()))(((())()()))(((()(()()(()())()))(()()())())))(()())(()((()()(())()()((()()()())()))())((((((()((()()(((()(()(()(())(((((((((()(())((())))(())())((())()()(((()))()()(((((((())(())))))))(())()"; 27207f6482 2016-05-12 kinaba: int __[] = {-2}; 27207f6482 2016-05-12 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); 27207f6482 2016-05-12 kinaba: END 27207f6482 2016-05-12 kinaba: /* 27207f6482 2016-05-12 kinaba: CASE(6) 27207f6482 2016-05-12 kinaba: string s = ; 27207f6482 2016-05-12 kinaba: int __[] = ; 27207f6482 2016-05-12 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); 27207f6482 2016-05-12 kinaba: END 27207f6482 2016-05-12 kinaba: */ 27207f6482 2016-05-12 kinaba: } 27207f6482 2016-05-12 kinaba: // END CUT HERE