Overview
| SHA1 Hash: | d7959f8d5d461e3f8951354bc2713ac479e1beb1 |
|---|---|
| Date: | 2014-07-22 10:38:02 |
| User: | kinaba |
| Comment: | 627 |
| 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/627-U/1A.cpp version [efb89f3f41758ae4]
> 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 HappyLetterDiv1 { public: > 23 string getHappyLetters(string letters) > 24 { > 25 set<char> cs(letters.begin(), letters.end()); > 26 string ans; > 27 for(char c: cs) > 28 if(can_win(c, letters)) > 29 ans += c; > 30 return ans; > 31 } > 32 > 33 bool can_win(char c, const string& s) > 34 { > 35 string rest; > 36 string cs; > 37 for(char ch: s) (ch==c ? cs : rest) += ch; > 38 > 39 if(rest.size()%2==1) { > 40 rest += c; > 41 cs.resize(cs.size()-1); > 42 } > 43 > 44 while(!cs.empty()) { > 45 if(can_erase(rest)) > 46 return true; > 47 if(cs.size()<2) > 48 break; > 49 rest += string(2, c); > 50 cs.resize(cs.size()-2); > 51 } > 52 return false; > 53 } > 54 > 55 bool can_erase(string s) > 56 { > 57 map<char, int> cnt; > 58 int maxCnt = 0; > 59 for(char c: s) maxCnt = max(maxCnt, ++cnt[c]); > 60 return maxCnt*2 <= s.size(); > 61 } > 62 }; > 63 > 64 // BEGIN CUT HERE > 65 #include <ctime> > 66 double start_time; string timer() > 67 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 68 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 69 { os << "{ "; > 70 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 71 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 72 void verify_case(const string& Expected, const string& Received) { > 73 bool ok = (Expected == Received); > 74 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 75 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 76 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 77 #define END verify_case(_, HappyLetterDiv1().getHappyLetters(letters));} > 78 int main(){ > 79 > 80 CASE(0) > 81 string letters = "aabbacccc"; > 82 string _ = "abc"; > 83 END > 84 CASE(1) > 85 string letters = "aaaaaaaccdd"; > 86 string _ = "a"; > 87 END > 88 CASE(2) > 89 string letters = "ddabccadb"; > 90 string _ = "abcd"; > 91 END > 92 CASE(3) > 93 string letters = "aaabbb"; > 94 string _ = ""; > 95 END > 96 CASE(4) > 97 string letters = "rdokcogscosn"; > 98 string _ = "cos"; > 99 END > 100 /* > 101 CASE(5) > 102 string letters = ; > 103 string _ = ; > 104 END > 105 CASE(6) > 106 string letters = ; > 107 string _ = ; > 108 END > 109 */ > 110 } > 111 // END CUT HERE
Added SRM/627-U/1B.cpp version [1e90d6c4d0058350]
> 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 static const int INF = 0x7fffffff; > 22 > 23 template<typename T=LL> > 24 struct FenwickTree > 25 { > 26 vector<T> x; > 27 FenwickTree(size_t n) : x(n) {} > 28 > 29 void incr( int k, const T& a ) { // z[k] += a; > 30 for(; k < x.size(); k|=k+1) > 31 x[k] += a; > 32 } > 33 T sum(int i, int j) { // Sigma z[i,j) excl. > 34 return sum_impl(j-1) - sum_impl(i-1); > 35 } > 36 T sum_impl(int j) { // Sigma z[0,j] incl. > 37 T v = T(); > 38 for(; j>=0; j=(j&(j+1))-1) > 39 v += x[j]; > 40 return v; > 41 } > 42 }; > 43 > 44 class GraphInversions { public: > 45 int getMinimumInversions(vector <int> A, vector <int> B, vector <int> V, > 46 { > 47 int N = A.size(); > 48 vector<vector<int>> G(N); > 49 for(int i=0; i<N; ++i) { > 50 int a=A[i], b=B[i]; > 51 G[a].push_back(b); > 52 G[b].push_back(a); > 53 } > 54 > 55 int best = INF; > 56 for(int s=0; s<N; ++s) > 57 best = min(best, solveRooted(K, s, N, G, V)); > 58 return (best==INF ? -1 : best); > 59 } > 60 > 61 int solveRooted(size_t K, int S, int N, const vector<vector<int>>& G, co > 62 { > 63 int best = INF; > 64 > 65 vector<bool> vis(N, false); > 66 FenwickTree<int> fw(1001); > 67 vector<int> score_stack; > 68 > 69 function<void(int)> rec; > 70 rec = [&](int v) { > 71 int s = (score_stack.empty() ? 0 : score_stack.back()); > 72 s += fw.sum(V[v]+1, 1001); > 73 fw.incr(V[v], 1); > 74 score_stack.push_back(s); > 75 > 76 if(score_stack.size() == K) { > 77 best = min(best, score_stack.back()); > 78 fw.incr(V[v], -1); > 79 score_stack.pop_back(); > 80 return; > 81 } > 82 > 83 vis[v] = true; > 84 for(int u: G[v]) if(!vis[u]) > 85 rec(u); > 86 vis[v] = false; > 87 fw.incr(V[v], -1); > 88 score_stack.pop_back(); > 89 }; > 90 rec(S); > 91 return best; > 92 } > 93 }; > 94 > 95 // BEGIN CUT HERE > 96 #include <ctime> > 97 double start_time; string timer() > 98 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 99 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 100 { os << "{ "; > 101 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 102 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 103 void verify_case(const int& Expected, const int& Received) { > 104 bool ok = (Expected == Received); > 105 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 106 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 107 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 108 #define END verify_case(_, GraphInversions().getMinimumInversions(A, B, V, > 109 int main(){ > 110 > 111 CASE(0) > 112 int A_[] = {0,1,2}; > 113 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 114 int B_[] = {1,2,0}; > 115 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 116 int V_[] = {40,50,60}; > 117 vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); > 118 int K = 3; > 119 int _ = 0; > 120 END > 121 CASE(1) > 122 int A_[] = {0,1,2,3}; > 123 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 124 int B_[] = {1,2,3,0}; > 125 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 126 int V_[] = {60,40,50,30}; > 127 vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); > 128 int K = 3; > 129 int _ = 1; > 130 END > 131 CASE(2) > 132 int A_[] = {0,1,2,3,0}; > 133 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 134 int B_[] = {1,2,3,0,4}; > 135 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 136 int V_[] = {10,10,10,5,5}; > 137 vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); > 138 int K = 5; > 139 int _ = 1; > 140 END > 141 CASE(3) > 142 int A_[] = {0,1,2,3,0,2}; > 143 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 144 int B_[] = {1,2,3,0,4,5}; > 145 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 146 int V_[] = {10,2,5,3,7,1}; > 147 vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); > 148 int K = 6; > 149 int _ = -1; > 150 END > 151 CASE(4) > 152 int A_[] = {5,7,7,5,5,7,6,4}; > 153 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 154 int B_[] = {2,0,2,0,1,4,7,3}; > 155 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 156 int V_[] = {15,10,5,30,22,10,5,2}; > 157 vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); > 158 int K = 6; > 159 int _ = 3; > 160 END > 161 CASE(4) > 162 int A_[] = {5,7,7,5,5,7,6,4}; > 163 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 164 int B_[] = {2,0,2,0,1,4,7,3}; > 165 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 166 int V_[] = {15,10,5,30,22,10,5,2}; > 167 vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); > 168 int K = 1; > 169 int _ = 0; > 170 END > 171 CASE(4) > 172 int A_[] = {5,7,7,5,5,7,6,4}; > 173 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 174 int B_[] = {2,0,2,0,1,4,7,3}; > 175 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 176 int V_[] = {15,10,5,30,22,10,5,2}; > 177 vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); > 178 int K = 2; > 179 int _ = 0; > 180 END > 181 CASE(5) > 182 int A_[] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,2 > 183 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 184 int B_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23, > 185 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 186 int V_[] = {137,1000,88,120,582,208,9,350,562,432,981,242,183,459,223,90 > 187 vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); > 188 int K = 1000; > 189 int _ = -1; > 190 END > 191 /* > 192 CASE(6) > 193 int A_[] = ; > 194 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 195 int B_[] = ; > 196 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 197 int V_[] = ; > 198 vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); > 199 int K = ; > 200 int _ = ; > 201 END > 202 */ > 203 } > 204 // END CUT HERE