Overview
| SHA1 Hash: | 6cfba8c225fce79b953deb9619fbaaacf4a09532 |
|---|---|
| Date: | 2015-12-10 11:05:24 |
| User: | kinaba |
| Comment: | 674 |
| 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/674-U/1A.cpp version [905f678193eee983]
> 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 VampireTree { public: > 23 int maxDistance(vector <int> num) > 24 { > 25 int d1 = 0, d_else = 0, d_kill = 0; > 26 for(int d: num) > 27 if(d == 1) > 28 d1++; > 29 else > 30 d_else++, d_kill+=d-2; > 31 if(d1-d_kill == 2) > 32 return d_else + 1; > 33 else > 34 return -1; > 35 } > 36 }; > 37 > 38 // BEGIN CUT HERE > 39 #include <ctime> > 40 double start_time; string timer() > 41 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 42 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 43 { os << "{ "; > 44 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 45 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 46 void verify_case(const int& Expected, const int& Received) { > 47 bool ok = (Expected == Received); > 48 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 49 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 50 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 51 #define END verify_case(_, VampireTree().maxDistance(num));} > 52 int main(){ > 53 > 54 CASE(0) > 55 int num_[] = {1, 2, 1}; > 56 vector <int> num(num_, num_+sizeof(num_)/sizeof(*num_)); > 57 int _ = 2; > 58 END > 59 CASE(1) > 60 int num_[] = {2, 2, 2}; > 61 vector <int> num(num_, num_+sizeof(num_)/sizeof(*num_)); > 62 int _ = -1; > 63 END > 64 CASE(2) > 65 int num_[] = {1, 1, 1, 1, 4}; > 66 vector <int> num(num_, num_+sizeof(num_)/sizeof(*num_)); > 67 int _ = 2; > 68 END > 69 CASE(3) > 70 int num_[] = {1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, > 71 vector <int> num(num_, num_+sizeof(num_)/sizeof(*num_)); > 72 int _ = -1; > 73 END > 74 /* > 75 CASE(4) > 76 int num_[] = ; > 77 vector <int> num(num_, num_+sizeof(num_)/sizeof(*num_)); > 78 int _ = ; > 79 END > 80 CASE(5) > 81 int num_[] = ; > 82 vector <int> num(num_, num_+sizeof(num_)/sizeof(*num_)); > 83 int _ = ; > 84 END > 85 */ > 86 > 87 } > 88 // END CUT HERE
Added SRM/674-U/1B.cpp version [dc438b5d9c04f458]
> 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 FindingKids { public: > 23 long long getSum(int n, int q, int A_, const int B, const int C) > 24 { > 25 set<int> pos_set; > 26 vector<int> pos(n), dir(n); > 27 > 28 const int M = 1000000007; > 29 LL A = A_; > 30 for(int i=0; i<n; ++i) { > 31 A = (A * B + C) % M; > 32 int p = int(A % (M - n + i + 1)); > 33 if(pos_set.count(p)) > 34 p = M - n + i; > 35 pos[i] = p; > 36 pos_set.insert(p); > 37 if(p%2 == 0) > 38 dir[i] = +1; > 39 else > 40 dir[i] = -1; > 41 } > 42 > 43 vector<int> kid(q), time(q); > 44 for(int i=0; i<q; ++i) { > 45 A = (A * B + C) % M; > 46 kid[i] = int(A%n); > 47 A = (A * B + C) % M; > 48 time[i] = int(A); > 49 } > 50 > 51 return solve(n, pos, dir, q, kid, time); > 52 } > 53 > 54 LL solve( > 55 const int N, const vector<int>& P, const vector<int>& D, > 56 const int Q, const vector<int>& K, const vector<int>& T) { > 57 > 58 vector<int> kid_id_to_pos_order(N); { > 59 vector<int> kids_sorted_by_pos(N); > 60 for(int i=0; i<N; ++i) kids_sorted_by_pos[i] = i; > 61 sort(kids_sorted_by_pos.begin(), kids_sorted_by_pos.end( > 62 return P[a] < P[b]; > 63 }); > 64 for(int i=0; i<N; ++i) > 65 kid_id_to_pos_order[kids_sorted_by_pos[i]] = i; > 66 } > 67 > 68 vector<LL> move_kids, stay_kids; > 69 for(int i=0; i<N; ++i) > 70 (D[i] == +1 ? move_kids : stay_kids).emplace_back(P[i]); > 71 > 72 sort(move_kids.begin(), move_kids.end()); > 73 sort(stay_kids.begin(), stay_kids.end()); > 74 > 75 LL total = 0; > 76 for(int i=0; i<Q; ++i) { > 77 LL p = find_kth_left(kid_id_to_pos_order[K[i]], stay_kid > 78 total += abs(p - T[i]); > 79 } > 80 return total; > 81 } > 82 > 83 // Find the $k$-th left kid in {stay_kids} U {move_kids += t}. > 84 LL find_kth_left(const int k, const vector<LL>& stay_kids, const vector< > 85 if(stay_kids.empty()) return move_kids[k]+t; > 86 if(move_kids.empty()) return stay_kids[k]; > 87 if(stay_kids.back() < move_kids.front()+t) { > 88 if(k < stay_kids.size()) > 89 return stay_kids[k]; > 90 else > 91 return move_kids[k-stay_kids.size()]+t; > 92 } > 93 if(move_kids.back()+t < stay_kids.front()) { > 94 if(k < move_kids.size()) > 95 return move_kids[k]+t; > 96 else > 97 return stay_kids[k-move_kids.size()]+t; > 98 } > 99 > 100 int L=0, R=stay_kids.size(); > 101 while(R-L>1) { > 102 int C = (L+R)/2; > 103 int left_in_stay = C; > 104 int left_in_move = lower_bound(move_kids.begin(), move_k > 105 int left = left_in_stay + left_in_move; > 106 if(left == k) > 107 return stay_kids[C]; > 108 (left >= k ? R : L) = C; > 109 } > 110 > 111 L=0, R=move_kids.size(); > 112 while(R-L>1) { > 113 int C = (L+R)/2; > 114 int left_in_move = C; > 115 int left_in_stay = lower_bound(stay_kids.begin(), stay_k > 116 int left = left_in_stay + left_in_move; > 117 if(left == k) > 118 return move_kids[C]+t; > 119 (left >= k ? R : L) = C; > 120 } > 121 > 122 vector<LL> now = stay_kids; > 123 for(LL p: move_kids) now.push_back(p + t); > 124 sort(now.begin(), now.end()); > 125 return now[k]; > 126 } > 127 }; > 128 > 129 // BEGIN CUT HERE > 130 #include <ctime> > 131 double start_time; string timer() > 132 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 133 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 134 { os << "{ "; > 135 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 136 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 137 void verify_case(const long long& Expected, const long long& Received) { > 138 bool ok = (Expected == Received); > 139 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 140 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 141 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 142 #define END verify_case(_, FindingKids().getSum(n, q, A, B, C));} > 143 int main(){ > 144 > 145 CASE(0) > 146 int n = 5; > 147 int q = 2; > 148 int A = 0; > 149 int B = 1; > 150 int C = 1; > 151 long long _ = 15LL; > 152 END > 153 CASE(1) > 154 int n = 5; > 155 int q = 4; > 156 int A = 3; > 157 int B = 2; > 158 int C = 1; > 159 long long _ = 43376LL; > 160 END > 161 CASE(2) > 162 int n = 200000; > 163 int q = 200000; > 164 int A = 12345; > 165 int B = 67890; > 166 int C = 111213141; > 167 long long _ = 133378408428237LL; > 168 END > 169 /* > 170 CASE(3) > 171 int n = ; > 172 int q = ; > 173 int A = ; > 174 int B = ; > 175 int C = ; > 176 long long _ = LL; > 177 END > 178 CASE(4) > 179 int n = ; > 180 int q = ; > 181 int A = ; > 182 int B = ; > 183 int C = ; > 184 long long _ = LL; > 185 END > 186 */ > 187 } > 188 // END CUT HERE
Added SRM/674-U/1C-U.cpp version [410a4764b987c8ec]
> 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 ClassicProblem { public: > 23 long long maximalValue(vector <int> cnt, vector <int> w, vector <int> v, > 24 { > 25 vector<int> idx; > 26 for(int i=0; i<cnt.size(); ++i) > 27 idx.push_back(i); > 28 sort(idx.begin(), idx.end(), [&](int a, int b) { > 29 // sort by increasing order of v[a]/w[a] > 30 if(LL(v[a])*w[b] == LL(v[b])*w[a]) > 31 return w[a]>w[b]; > 32 return LL(v[a])*w[b] < LL(v[b])*w[a]; > 33 }); > 34 > 35 LL gain = 0; > 36 while(limit > 6480) { > 37 if(idx.empty()) > 38 break; > 39 int i = idx.back(), ww=w[i], vv=v[i]; > 40 int n = min(cnt[i], (limit-6400)/ww); > 41 limit -= LL(ww)*n; > 42 gain += LL(vv)*n; > 43 cnt[i] -= n; > 44 idx.pop_back(); > 45 } > 46 > 47 vector<LL> w2v = rec(0, cnt, w, v, limit); > 48 return gain + *max_element(w2v.begin(), w2v.end()); > 49 } > 50 > 51 vector<LL> rec(int i, const vector <int>& C, const vector<int>& W, const > 52 { > 53 if(i == C.size()) > 54 return vector<LL>(1, 0LL); > 55 > 56 vector<LL> w2v = rec(i+1, C, W, V, limit); > 57 if(C[i] == 0) > 58 return w2v; > 59 > 60 vector<LL> w2v_neo(limit+1, 0LL); > 61 for(int w=0; w<w2v.size(); ++w) { > 62 for(int k=0; k<=C[i]; ++k) { // this type of typical DP > 63 int ww = w + LL(W[i])*k; > 64 if(ww > limit) > 65 break; > 66 w2v_neo[ww] = max(w2v_neo[ww], w2v[w] + LL(V[i]) > 67 } > 68 } > 69 return w2v_neo; > 70 } > 71 }; > 72 > 73 // BEGIN CUT HERE > 74 #include <ctime> > 75 double start_time; string timer() > 76 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 77 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 78 { os << "{ "; > 79 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 80 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 81 void verify_case(const long long& Expected, const long long& Received) { > 82 bool ok = (Expected == Received); > 83 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 84 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 85 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 86 #define END verify_case(_, ClassicProblem().maximalValue(cnt, w, v, limit)) > 87 int main(){ > 88 > 89 CASE(0) > 90 int cnt_[] = {100,100}; > 91 vector <int> cnt(cnt_, cnt_+sizeof(cnt_)/sizeof(*cnt_)); > 92 int w_[] = {2,3}; > 93 vector <int> w(w_, w_+sizeof(w_)/sizeof(*w_)); > 94 int v_[] = {3,5}; > 95 vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); > 96 int limit = 6; > 97 long long _ = 10LL; > 98 END > 99 CASE(1) > 100 int cnt_[] = {100,100}; > 101 vector <int> cnt(cnt_, cnt_+sizeof(cnt_)/sizeof(*cnt_)); > 102 int w_[] = {2,3}; > 103 vector <int> w(w_, w_+sizeof(w_)/sizeof(*w_)); > 104 int v_[] = {3,5}; > 105 vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); > 106 int limit = 5; > 107 long long _ = 8LL; > 108 END > 109 CASE(2) > 110 int cnt_[] = {100,102}; > 111 vector <int> cnt(cnt_, cnt_+sizeof(cnt_)/sizeof(*cnt_)); > 112 int w_[] = {2,3}; > 113 vector <int> w(w_, w_+sizeof(w_)/sizeof(*w_)); > 114 int v_[] = {3,5}; > 115 vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); > 116 int limit = 1000000000; > 117 long long _ = 810LL; > 118 END > 119 CASE(3) > 120 int cnt_[] = {100,100}; > 121 vector <int> cnt(cnt_, cnt_+sizeof(cnt_)/sizeof(*cnt_)); > 122 int w_[] = {2,3}; > 123 vector <int> w(w_, w_+sizeof(w_)/sizeof(*w_)); > 124 int v_[] = {3,5}; > 125 vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); > 126 int limit = 1; > 127 long long _ = 0LL; > 128 END > 129 CASE(4) > 130 int cnt_[] = {1,2,3,4,5,6,7,8}; > 131 vector <int> cnt(cnt_, cnt_+sizeof(cnt_)/sizeof(*cnt_)); > 132 int w_[] = {4,2,6,7,5,8,3,1}; > 133 vector <int> w(w_, w_+sizeof(w_)/sizeof(*w_)); > 134 int v_[] = {3,6,4,1,2,8,5,7}; > 135 vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); > 136 int limit = 15; > 137 long long _ = 73LL; > 138 END > 139 CASE(5) > 140 int cnt_[] = {1000000000}; > 141 vector <int> cnt(cnt_, cnt_+sizeof(cnt_)/sizeof(*cnt_)); > 142 int w_[] = {1}; > 143 vector <int> w(w_, w_+sizeof(w_)/sizeof(*w_)); > 144 int v_[] = {1000000000}; > 145 vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); > 146 int limit = 1000000000; > 147 long long _ = 1000000000000000000LL; > 148 END > 149 /* > 150 CASE(6) > 151 int cnt_[] = ; > 152 vector <int> cnt(cnt_, cnt_+sizeof(cnt_)/sizeof(*cnt_)); > 153 int w_[] = ; > 154 vector <int> w(w_, w_+sizeof(w_)/sizeof(*w_)); > 155 int v_[] = ; > 156 vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); > 157 int limit = ; > 158 long long _ = LL; > 159 END > 160 CASE(7) > 161 int cnt_[] = ; > 162 vector <int> cnt(cnt_, cnt_+sizeof(cnt_)/sizeof(*cnt_)); > 163 int w_[] = ; > 164 vector <int> w(w_, w_+sizeof(w_)/sizeof(*w_)); > 165 int v_[] = ; > 166 vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); > 167 int limit = ; > 168 long long _ = LL; > 169 END > 170 */ > 171 } > 172 // END CUT HERE