Overview
| SHA1 Hash: | 37b91b57bc96ea6fe392dbb0114409910dbbc27e |
|---|---|
| Date: | 2014-07-10 14:23:48 |
| User: | kinaba |
| Comment: | 3C |
| 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/TCO13-3C-U/1A.cpp version [03422e036f8b28bb]
> 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 SubstringReversal { public: > 23 vector <int> solve(string S) > 24 { > 25 multiset<char> chars; > 26 for(char c: S) chars.insert(c); > 27 > 28 string T = S; > 29 for(int i=0; i<S.size(); ++i) { > 30 if(S[i] == *chars.begin()) { > 31 chars.erase(chars.begin()); > 32 continue; > 33 } > 34 > 35 // here is the point. > 36 int best_k = i; > 37 string best = S.substr(i); > 38 for(int k=i+1; k<S.size(); ++k) { > 39 string T(S.begin()+i, S.begin()+k+1); > 40 reverse(T.begin(), T.end()); > 41 T += S.substr(k+1); > 42 if(best > T) > 43 best=T, best_k=k; > 44 } > 45 vector<int> ans; > 46 ans.push_back(i); > 47 ans.push_back(best_k); > 48 return ans; > 49 } > 50 > 51 // no need to reverse > 52 vector<int> ans; > 53 ans.push_back(0); > 54 ans.push_back(0); > 55 return ans; > 56 } > 57 }; > 58 > 59 // BEGIN CUT HERE > 60 #include <ctime> > 61 double start_time; string timer() > 62 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 63 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 64 { os << "{ "; > 65 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 66 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 67 void verify_case(const vector <int>& Expected, const vector <int>& Received) { > 68 bool ok = (Expected == Received); > 69 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 70 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 71 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 72 #define END verify_case(_, SubstringReversal().solve(S));} > 73 int main(){ > 74 > 75 CASE(0) > 76 string S = "abdc"; > 77 int __[] = {2, 3 }; > 78 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 79 END > 80 CASE(1) > 81 string S = "aabbcc"; > 82 int __[] = {0, 0 }; > 83 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 84 END > 85 CASE(2) > 86 string S = "misof"; > 87 int __[] = {0, 4 }; > 88 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 89 END > 90 CASE(3) > 91 string S = "ivan"; > 92 int __[] = {0, 2 }; > 93 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 94 END > 95 CASE(4) > 96 string S = "thisseemstobeaneasyproblem"; > 97 int __[] = {0, 13 }; > 98 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 99 END > 100 /* > 101 CASE(5) > 102 string S = ; > 103 int __[] = ; > 104 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 105 END > 106 CASE(6) > 107 string S = ; > 108 int __[] = ; > 109 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 110 END > 111 */ > 112 } > 113 // END CUT HERE
Added SRM/TCO13-3C-U/1B.cpp version [f7dc591b0d55c297]
> 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 CliqueGraph { public: > 23 long long calcSum(int N, vector <int> V, vector <int> sizes) > 24 { > 25 vector<vector<int>> v2c(N); > 26 vector<vector<int>> c2v(sizes.size()); > 27 for(int s=0,i=0; i<sizes.size(); ++i) { > 28 int e = s+sizes[i]; > 29 for(int k=s; k<e; ++k) { > 30 v2c[V[k]].push_back(i); > 31 c2v[i].push_back(V[k]); > 32 } > 33 s = e; > 34 } > 35 > 36 LL total = 0; > 37 for(int v=0; v<N; ++v) > 38 total += calc(v, v2c, c2v); > 39 return total / 2; > 40 } > 41 > 42 LL calc(int S, const vector<vector<int>>& v2c, const vector<vector<int>> > 43 { > 44 const int V = v2c.size(), C = c2v.size(); > 45 vector<int> v_d(V, -1); > 46 vector<bool> c_visited(C, false); > 47 vector<int> q(1, S); > 48 v_d[S] = 0; > 49 for(int step=1; !q.empty(); step++) { > 50 vector<int> cq; > 51 for(int v: q) > 52 for(int c: v2c[v]) if(!c_visited[c]) > 53 cq.push_back(c), c_visited[c]=true; > 54 vector<int> q2; > 55 for(int c: cq) > 56 for(int v: c2v[c]) if(v_d[v]<0) > 57 q2.push_back(v), v_d[v]=step; > 58 q = std::move(q2); > 59 } > 60 > 61 LL total = 0; > 62 for(int d: v_d) > 63 total += d; > 64 return total; > 65 } > 66 }; > 67 > 68 // BEGIN CUT HERE > 69 #include <ctime> > 70 double start_time; string timer() > 71 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 72 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 73 { os << "{ "; > 74 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 75 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 76 void verify_case(const long long& Expected, const long long& Received) { > 77 bool ok = (Expected == Received); > 78 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 79 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 80 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 81 #define END verify_case(_, CliqueGraph().calcSum(N, V, sizes));} > 82 int main(){ > 83 > 84 CASE(0) > 85 int N = 4; > 86 int V_[] = {0,1,2,0,3}; > 87 vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); > 88 int sizes_[] = {3,2}; > 89 vector <int> sizes(sizes_, sizes_+sizeof(sizes_)/sizeof(*sizes_)); > 90 long long _ = 8LL; > 91 END > 92 CASE(1) > 93 int N = 5; > 94 int V_[] = {0,1,2,3,1,2,4}; > 95 vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); > 96 int sizes_[] = {4,3}; > 97 vector <int> sizes(sizes_, sizes_+sizeof(sizes_)/sizeof(*sizes_)); > 98 long long _ = 12LL; > 99 END > 100 CASE(2) > 101 int N = 15; > 102 int V_[] = {1,3,5,7,9,11,13,0 > 103 ,2,3,6,7,10,11,14,0 > 104 ,4,5,6,7,12,13,14,0 > 105 ,8,9,10,11,12,13,14,0}; > 106 vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); > 107 int sizes_[] = {8,8,8,8}; > 108 vector <int> sizes(sizes_, sizes_+sizeof(sizes_)/sizeof(*sizes_)); > 109 long long _ = 130LL; > 110 END > 111 /* > 112 CASE(3) > 113 int N = ; > 114 int V_[] = ; > 115 vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); > 116 int sizes_[] = ; > 117 vector <int> sizes(sizes_, sizes_+sizeof(sizes_)/sizeof(*sizes_)); > 118 long long _ = LL; > 119 END > 120 CASE(4) > 121 int N = ; > 122 int V_[] = ; > 123 vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); > 124 int sizes_[] = ; > 125 vector <int> sizes(sizes_, sizes_+sizeof(sizes_)/sizeof(*sizes_)); > 126 long long _ = LL; > 127 END > 128 */ > 129 } > 130 // END CUT HERE
Added SRM/TCO13-3C-U/1C-U.cpp version [aff45afb5a80e9b5]
> 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 InverseRMQ { public: > 23 string possible(int n, vector <int> A, vector <int> B, vector <int> ans) > 24 { > 25 vector<tuple<int,int,int>> E; > 26 for(int i=0; i<A.size(); ++i) > 27 E.emplace_back(A[i], B[i], ans[i]); > 28 sort(E.begin(), E.end(), [&](const tuple<int,int,int>& lhs, cons > 29 if(get<2>(lhs) < get<2>(rhs)) > 30 return true; > 31 return lhs < rhs; > 32 }); > 33 > 34 vector<pair<int,int>> filled; > 35 for(int i=0; i<E.size(); ) > 36 { > 37 int nexti = i+1; > 38 for(; nexti<E.size(); ++nexti) > 39 if(get<2>(E[i]) != get<2>(E[nexti])) > 40 break; > 41 // inner > 42 int L = get<0>(E[i]); > 43 int R = get<1>(E[i]); > 44 // outer > 45 int l = get<0>(E[i]); > 46 int r = get<1>(E[i]); > 47 for(int a=i+1; a<nexti; ++a) { > 48 if(R<get<0>(E[a]) || get<1>(E[a])<L) > 49 return "Impossible"; > 50 L = max(L, get<0>(E[a])); > 51 R = min(R, get<1>(E[a])); > 52 l = min(l, get<0>(E[a])); > 53 r = max(r, get<1>(E[a])); > 54 } > 55 > 56 bool ok = false; > 57 if(filled.empty()) ok = true; > 58 if(!ok && has_intersection(L,R,0,filled.front().first-1) > 59 if(!ok && has_intersection(L,R,filled.back().second+1,n) > 60 if(!ok) { > 61 for(int i=0; i+1<filled.size(); ++i) > 62 if(!ok && has_intersection(L,R,filled[i] > 63 ok=true; > 64 } > 65 if(!ok) > 66 return "Impossible"; > 67 > 68 int C = get<2>(E[i]); > 69 > 70 // check: enough number of elements for [l,r] > 71 int space = 0; > 72 > 73 > 74 // update > 75 filled.emplace_back(l, r); > 76 sort(filled.begin(), filled.end()); > 77 vector<pair<int,int>> f2; > 78 filled = f2; > 79 for(auto r: filled) { > 80 if(f2.empty() || f2.back().second+1 < r.first) > 81 f2.push_back(r); > 82 else > 83 f2.back().second = max(f2.back().second, > 84 } > 85 > 86 i = nexti; > 87 } > 88 return "Possible"; > 89 } > 90 > 91 static bool has_intersection(int a, int b, int A, int B) > 92 { > 93 return !(B<a || b<A); > 94 } > 95 }; > 96 > 97 // BEGIN CUT HERE > 98 #include <ctime> > 99 double start_time; string timer() > 100 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 101 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 102 { os << "{ "; > 103 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 104 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 105 void verify_case(const string& Expected, const string& Received) { > 106 bool ok = (Expected == Received); > 107 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 108 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 109 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 110 #define END verify_case(_, InverseRMQ().possible(n, A, B, ans));} > 111 int main(){ > 112 > 113 CASE(0) > 114 int n = 5; > 115 int A_[] = {1,2,4}; > 116 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 117 int B_[] = {2,4,5}; > 118 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 119 int ans_[] = {3,4,5}; > 120 vector <int> ans(ans_, ans_+sizeof(ans_)/sizeof(*ans_)); > 121 string _ = "Possible"; > 122 END > 123 CASE(1) > 124 int n = 3; > 125 int A_[] = {1,2,3}; > 126 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 127 int B_[] = {1,2,3}; > 128 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 129 int ans_[] = {3,3,3}; > 130 vector <int> ans(ans_, ans_+sizeof(ans_)/sizeof(*ans_)); > 131 string _ = "Impossible"; > 132 END > 133 CASE(2) > 134 int n = 600; > 135 int A_[] = {1,101,201,301,401,501}; > 136 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 137 int B_[] = {100,200,300,400,500,600}; > 138 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 139 int ans_[] = {100,200,300,400,500,600}; > 140 vector <int> ans(ans_, ans_+sizeof(ans_)/sizeof(*ans_)); > 141 string _ = "Possible"; > 142 END > 143 CASE(3) > 144 int n = 1000000000; > 145 int A_[] = {1234,1234}; > 146 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 147 int B_[] = {5678,5678}; > 148 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 149 int ans_[] = {10000,20000}; > 150 vector <int> ans(ans_, ans_+sizeof(ans_)/sizeof(*ans_)); > 151 string _ = "Impossible"; > 152 END > 153 CASE(4) > 154 int n = 8; > 155 int A_[] = {1,2,3,4,5,6,7,8}; > 156 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 157 int B_[] = {1,2,3,4,5,6,7,8}; > 158 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 159 int ans_[] = {4,8,2,5,6,3,7,1}; > 160 vector <int> ans(ans_, ans_+sizeof(ans_)/sizeof(*ans_)); > 161 string _ = "Possible"; > 162 END > 163 CASE(5) > 164 int n = 1000000000; > 165 int A_[] = {1}; > 166 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 167 int B_[] = {1000000000}; > 168 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 169 int ans_[] = {19911120}; > 170 vector <int> ans(ans_, ans_+sizeof(ans_)/sizeof(*ans_)); > 171 string _ = "Impossible"; > 172 END > 173 CASE(6) > 174 int n = ; > 175 int A_[] = ; > 176 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 177 int B_[] = ; > 178 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 179 int ans_[] = ; > 180 vector <int> ans(ans_, ans_+sizeof(ans_)/sizeof(*ans_)); > 181 string _ = ; > 182 END > 183 CASE(7) > 184 int n = ; > 185 int A_[] = ; > 186 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 187 int B_[] = ; > 188 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 189 int ans_[] = ; > 190 vector <int> ans(ans_, ans_+sizeof(ans_)/sizeof(*ans_)); > 191 string _ = ; > 192 END > 193 > 194 } > 195 // END CUT HERE