• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Added SRM/688-U/1A-U.cpp version [a37ca3e9fed3b6d2]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <tuple>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class ParenthesesDiv1Easy { public:
           23  + vector <int> correct(string s)
           24  + {
           25  +  if(s.length()%2 == 1)
           26  +   return vector<int>(1, -1);
           27  +
           28  +  vector<int> ans;
           29  +
           30  +  int d = 0;
           31  +  int peak = 0, peak_i = -1;
           32  +  for(int i=0; i<s.size(); ++i) {
           33  +   if(d == 0 && s[i]==')') {
           34  +    int sec_s = i;
           35  +    int sec_d = -1;
           36  +    int bot=-1, bot_k=i;
           37  +    for(int k=sec_s+1; sec_d<0 && k<s.size(); ++k) {
           38  +     sec_d += (s[k]=='(' ? +1 : -1);
           39  +     if(bot>sec_d) { bot=sec_d, bot_k=k; }
           40  +    }
           41  +    ans.push_back(sec_s);
           42  +    ans.push_back(bot_k);
           43  +    reverse(s.begin()+sec_s, s.begin()+bot_k+1);
           44  +    for(auto it=s.begin()+sec_s; it!=s.begin()+bot_k+1; ++it)
           45  +     *it=(*it=='(' ? ')' : '(');
           46  +    --i;
           47  +   } else {
           48  +    d += (s[i]=='(' ? +1 : -1);
           49  +    if(peak<d) { peak=d; peak_i=i; }
           50  +   }
           51  +  }
           52  +
           53  +  int back = d/2;
           54  +  if(back) {
           55  +   int p=peak_i, d=peak;
           56  +   for(;; --p) {
           57  +    d -= (s[p]=='(' ? +1 : -1);
           58  +    if(d==peak-back) {
           59  +     ans.push_back(p);
           60  +     ans.push_back(peak_i);
           61  +     break;
           62  +    }
           63  +   }
           64  +  }
           65  +
           66  +  return ans.size()>10 ? vector<int>(1, -1) : ans;
           67  + }
           68  +};
           69  +
           70  +// BEGIN CUT HERE
           71  +#include <ctime>
           72  +double start_time; string timer()
           73  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           74  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           75  + { os << "{ ";
           76  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           77  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           78  +void verify_case(const vector <int>& Expected, const vector <int>& Received) {
           79  + bool ok = (Expected == Received);
           80  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           81  + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
           82  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           83  +#define END  verify_case(_, ParenthesesDiv1Easy().correct(s));}
           84  +int main(){
           85  +
           86  +CASE(0)
           87  + string s = ")(";
           88  + int __[] = {0, 0, 1, 1 };
           89  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
           90  +END
           91  +CASE(1)
           92  + string s = "))))))((((((";
           93  + int __[] = {0, 5, 6, 11 };
           94  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
           95  +END
           96  +CASE(2)
           97  + string s = "))()())()";
           98  + int __[] = {-1 };
           99  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          100  +END
          101  +CASE(3)
          102  + string s = ")()(((";
          103  + int __[] = {0, 0, 3, 3, 5, 5 };
          104  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          105  +END
          106  +CASE(4)
          107  + string s = "()";
          108  + vector <int> _;
          109  +END
          110  +CASE(5)
          111  + string s = "))))()))(((()()((()()))))(())))(()()))))))())))))()()(()()(()))())((()))()((())))()())((()())(()(())))())()(()(()(()))))())))((()((())((()())(()())(()))((()()(()(()))((((((((((())((((()())()(()()())()(((((((()()())(()))(()())))))())((((())()(())(((()((()(())))(()((()())(((((()(()())(((()))()))(((()()()))()())))(())(())(()))))())(()))))()(()(()())(()())((()))()()((())(((()(((()(()()((())())())((()))))())((((())(()()()())(((((())(((())))))())()))()())())))(()()())((((()()))))())())())()())((()))(()(()))()(())))(()))()))(())((()())())())((((())))(()())())))(()((())()()())()))()))())(())((((()()((()(()())()(((()))))(()()()))())))(()())(())())(()))()())((()))((())))()((())(()))))))()(()(((()())(())(()((()((((())))((())))))()))()(()())()())))())(())))((()))()))(()()))())(()(())((()(()))((((()()())())(()))(((())()()))(((()(()()(()())()))(()()())())))(()())(()((()()(())()()((()()()())()))())((((((()((()()(((()(()(()(())(((((((((()(())((())))(())())((())()()(((()))()()(((((((())(())))))))(())()";
          112  +int __[] = {-2};
          113  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          114  +END
          115  +/*
          116  +CASE(6)
          117  + string s = ;
          118  + int __[] = ;
          119  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          120  +END
          121  +*/
          122  +}
          123  +// END CUT HERE

Added SRM/688-U/1B-U.cpp version [8c0d6d5b4a25753e]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <tuple>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class ParenthesesDiv1Medium { public:
           23  + int minSwaps(string s, vector <int> L, vector <int> R)
           24  + {
           25  +  set<pair<int,int>> LR;
           26  +  for(int i=0; i<L.size(); ++i) {
           27  +   if((R[i]-L[i]+1)%2==1)
           28  +    return -1;
           29  +   LR.emplace(L[i], R[i]+1);
           30  +  }
           31  +
           32  +  // event <pos, open>
           33  +  deque<pair<int,bool>> events;
           34  +  for(auto lr: LR) {
           35  +   events.emplace_back(lr.first, true);
           36  +   events.emplace_back(lr.second, false);
           37  +  }
           38  +  sort(events.begin(), events.end());
           39  +
           40  +  vector<string> req;
           41  +
           42  +  stack<string> stk;
           43  +  stk.push("");
           44  +  for(int i=0; i<=s.size(); ++i) {
           45  +   while(!events.empty() && events[0].first==i) {
           46  +    if(events[0].second) {
           47  +     stk.push("");
           48  +    } else {
           49  +     if(!stk.top().empty())
           50  +      req.push_back(stk.top());
           51  +     stk.pop();
           52  +    }
           53  +    events.pop_front();
           54  +   }
           55  +   if(i<s.size())
           56  +    stk.top() += s[i];
           57  +  }
           58  +
           59  +  return solve(req, stk.top());
           60  + }
           61  +
           62  + int sig(const string& s)
           63  + {
           64  +  int d = 0;
           65  +  for(char c: s) d += (c=='(' ? +1 : -1);
           66  +  return d;
           67  + }
           68  +
           69  + // required to make |require| strings correct, |remaining| is the unconstrained supply of chars.
           70  + int solve(const vector<string>& require, const string& remaining)
           71  + {
           72  +  //cerr << "[" << remaining << "]" << endl;
           73  +
           74  +  int cost = 0;
           75  +
           76  +  vector<int> sv;
           77  +  for(auto r: require)
           78  +  {
           79  +   int sr = sig(r)/2;
           80  +   sv.push_back(sr);
           81  +
           82  +   //cerr << ":: ["  << r << "] @ " << sr << endl;
           83  +
           84  +   int d = 0;
           85  +   for(char& c: r)
           86  +   {
           87  +    if(sr>0 && d>0 && c=='(') c=')', --sr;
           88  +    else if(sr<0 && c==')') c='(', ++sr;
           89  +    d += (c=='(' ? +1 : -1);
           90  +   }
           91  +   cost += cost_single(r);
           92  +  }
           93  +
           94  +  int ss = accumulate(sv.begin(), sv.end(), 0);
           95  +  if(ss>0 && ss>count(remaining.begin(), remaining.end(), ')')) return -1;
           96  +  if(ss<0 && -ss>count(remaining.begin(), remaining.end(), '(')) return -1;
           97  +
           98  +  int nega=0, posi=0; for(int z: sv) if(z<0) nega+=-z; else posi+=z;
           99  +  return cost + max(nega, posi);
          100  + }
          101  +
          102  + int cost_single(string r)
          103  + {
          104  +  int cost = 0;
          105  +  int d = 0;
          106  +  for(char c: r) {
          107  +   d += (c=='(' ? +1 : -1);
          108  +   if(d==-1) ++cost, d=+1;
          109  +  }
          110  +  return cost;
          111  + }
          112  +};
          113  +
          114  +// BEGIN CUT HERE
          115  +#include <ctime>
          116  +double start_time; string timer()
          117  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          118  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          119  + { os << "{ ";
          120  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          121  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          122  +void verify_case(const int& Expected, const int& Received) {
          123  + bool ok = (Expected == Received);
          124  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          125  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          126  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          127  +#define END  verify_case(_, ParenthesesDiv1Medium().minSwaps(s, L, R));}
          128  +int main(){
          129  +
          130  +CASE(0)
          131  + string s = ")(";
          132  + int L_[] = {0,0,0,0};
          133  +   vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_));
          134  + int R_[] = {1,1,1,1};
          135  +   vector <int> R(R_, R_+sizeof(R_)/sizeof(*R_));
          136  + int _ = 1;
          137  +END
          138  +CASE(1)
          139  + string s = "(())";
          140  + int L_[] = {0,2};
          141  +   vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_));
          142  + int R_[] = {1,3};
          143  +   vector <int> R(R_, R_+sizeof(R_)/sizeof(*R_));
          144  + int _ = 1;
          145  +END
          146  +CASE(2)
          147  + string s = "(((())";
          148  + int L_[] = {0,2};
          149  +   vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_));
          150  + int R_[] = {1,3};
          151  +   vector <int> R(R_, R_+sizeof(R_)/sizeof(*R_));
          152  + int _ = 2;
          153  +END
          154  +CASE(3)
          155  + string s = "(((((((((";
          156  + int L_[] = {0,2};
          157  +   vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_));
          158  + int R_[] = {1,3};
          159  +   vector <int> R(R_, R_+sizeof(R_)/sizeof(*R_));
          160  + int _ = -1;
          161  +END
          162  +CASE(4)
          163  + string s = "()()()()";
          164  + int L_[] = {0,0,0,0,2,2,2,4,4,6};
          165  +   vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_));
          166  + int R_[] = {1,3,5,7,3,5,7,5,7,7};
          167  +   vector <int> R(R_, R_+sizeof(R_)/sizeof(*R_));
          168  + int _ = 0;
          169  +END
          170  +CASE(5)
          171  + string s = ")()(()()((())()()()()()()))(()())()()()(";
          172  + int L_[] = {3,5,17,25,35};
          173  +   vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_));
          174  + int R_[] = {12,10,30,30,38};
          175  +   vector <int> R(R_, R_+sizeof(R_)/sizeof(*R_));
          176  + int _ = 3;
          177  +END
          178  +/*
          179  +CASE(6)
          180  + string s = ;
          181  + int L_[] = ;
          182  +   vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_));
          183  + int R_[] = ;
          184  +   vector <int> R(R_, R_+sizeof(R_)/sizeof(*R_));
          185  + int _ = ;
          186  +END
          187  +CASE(7)
          188  + string s = ;
          189  + int L_[] = ;
          190  +   vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_));
          191  + int R_[] = ;
          192  +   vector <int> R(R_, R_+sizeof(R_)/sizeof(*R_));
          193  + int _ = ;
          194  +END
          195  +*/
          196  +}
          197  +// END CUT HERE