Overview
| SHA1 Hash: | 27207f64829aca237d7fddf23d38ff86e61577d3 |
|---|---|
| Date: | 2016-05-12 13:35:03 |
| User: | kinaba |
| Comment: | 688 |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
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 > 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) > 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 > 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() > 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 uncons > 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(), ')')) re > 96 if(ss<0 && -ss>count(remaining.begin(), remaining.end(), '(')) r > 97 > 98 int nega=0, posi=0; for(int z: sv) if(z<0) nega+=-z; else posi+= > 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) > 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 > 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() > 125 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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