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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 49 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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, 17, 18, 19}; 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(), [&](int a, int b){ 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_kids, move_kids, 2*T[i]); 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<LL>& move_kids, const LL t) { 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_kids.end(), stay_kids[C]-t) - move_kids.begin(); 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_kids.end(), move_kids[C]+t) - stay_kids.begin(); 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 140 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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, int limit) 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 vector<int>& V, int limit) 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 can be faster 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])*k); 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 84 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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