Overview
| SHA1 Hash: | 054a0e8c069b30cc587ff3bd5358d082677bf7c5 |
|---|---|
| Date: | 2014-09-26 00:46:07 |
| User: | kinaba |
| Comment: | 633 |
| 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/633-U/1A.cpp version [7bd18a955be38dea]
> 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 PeriodicJumping { public: > 23 int minimalTime(int x, vector <int> jumpLengths) > 24 { > 25 if(x==0) > 26 return 0; > 27 if(x<0) > 28 x=-x; > 29 > 30 vector<int> js; > 31 js.insert(js.end(), jumpLengths.begin(), jumpLengths.end()); > 32 js.insert(js.end(), jumpLengths.begin(), jumpLengths.end()); > 33 const LL all_sum = accumulate(js.begin(), js.end(), 0LL); > 34 > 35 LL best = 1LL<<62; > 36 for(int i=0; i<js.size(); ++i) > 37 { > 38 LL sum = accumulate(js.begin(), js.begin()+i+1, 0LL); > 39 LL M = *max_element(js.begin(), js.begin()+i+1); > 40 LL min_repr = max(0LL, M*2-sum); > 41 > 42 // [min_repr, sum] in the first round. > 43 if(min_repr<=x && x<=sum) > 44 best = min<LL>(best, i+1); > 45 // [0, sum+K*all_sum] in the Kth round. > 46 LL K = max(1LL, (x-sum+all_sum-1)/all_sum); > 47 best = min<LL>(best, K*js.size()+i+1); > 48 } > 49 return int(best); > 50 } > 51 }; > 52 > 53 // BEGIN CUT HERE > 54 #include <ctime> > 55 double start_time; string timer() > 56 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 57 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 58 { os << "{ "; > 59 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 60 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 61 void verify_case(const int& Expected, const int& Received) { > 62 bool ok = (Expected == Received); > 63 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 64 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 65 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 66 #define END verify_case(_, PeriodicJumping().minimalTime(x, jumpLengths));} > 67 int main(){ > 68 > 69 CASE(0) > 70 int x = 15; > 71 int jumpLengths_[] = {1,2,3,4,5,6,7,8,9,10}; > 72 vector <int> jumpLengths(jumpLengths_, jumpLengths_+sizeof(jumpLengths > 73 int _ = 5; > 74 END > 75 CASE(1) > 76 int x = 5; > 77 int jumpLengths_[] = {5}; > 78 vector <int> jumpLengths(jumpLengths_, jumpLengths_+sizeof(jumpLengths > 79 int _ = 1; > 80 END > 81 CASE(2) > 82 int x = 1; > 83 int jumpLengths_[] = {10}; > 84 vector <int> jumpLengths(jumpLengths_, jumpLengths_+sizeof(jumpLengths > 85 int _ = 2; > 86 END > 87 CASE(3) > 88 int x = -10; > 89 int jumpLengths_[] = {2,3,4,500,6,7,8}; > 90 vector <int> jumpLengths(jumpLengths_, jumpLengths_+sizeof(jumpLengths > 91 int _ = 11; > 92 END > 93 CASE(4) > 94 int x = -1000000000; > 95 int jumpLengths_[] = {1}; > 96 vector <int> jumpLengths(jumpLengths_, jumpLengths_+sizeof(jumpLengths > 97 int _ = 1000000000; > 98 END > 99 CASE(5) > 100 int x = 0; > 101 int jumpLengths_[] = {19911120}; > 102 vector <int> jumpLengths(jumpLengths_, jumpLengths_+sizeof(jumpLengths > 103 int _ = 0; > 104 END > 105 /* > 106 CASE(6) > 107 int x = ; > 108 int jumpLengths_[] = ; > 109 vector <int> jumpLengths(jumpLengths_, jumpLengths_+sizeof(jumpLengths > 110 int _ = ; > 111 END > 112 CASE(7) > 113 int x = ; > 114 int jumpLengths_[] = ; > 115 vector <int> jumpLengths(jumpLengths_, jumpLengths_+sizeof(jumpLengths > 116 int _ = ; > 117 END > 118 */ > 119 } > 120 // END CUT HERE
Added SRM/633-U/1B-U.cpp version [cfb3baca4827166b]
> 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 DoubleTree { public: > 23 int maximalScore(vector <int> a, vector <int> b, vector <int> c, vector > 24 { > 25 const int N = a.size() + 1; > 26 > 27 vector<vector<LL>> dep(N, vector<LL>(N)); > 28 add_dep(a, b, dep); > 29 add_dep(c, d, dep); > 30 closure(N, dep); > 31 > 32 int best = 0; > 33 for(int root=0; root<N; ++root) > 34 { > 35 int base_score = score[root]; > 36 > 37 set<LL> cs; > 38 for(int v=0; v<N; ++v) if(v!=root) > 39 cs.insert(dep[min(root,v)][max(root,v)] &~ (1LL< > 40 > 41 LL theSet = 0; > 42 for(LL c: cs) { > 43 int ss = 0; > 44 for(int i=0; (1LL<<i)<=c; ++i) > 45 if((1LL<<i)&c) > 46 ss += score[i]; > 47 if(ss>0) > 48 theSet |= c; > 49 } > 50 > 51 int ss = 0; > 52 for(int i=0; (1LL<<i)<=theSet; ++i) > 53 if((1LL<<i)&theSet) > 54 ss += score[i]; > 55 best = max(best, base_score+ss); > 56 } > 57 return best; > 58 } > 59 > 60 void closure(int N, vector<vector<LL>>& dep) > 61 { > 62 for(bool upd=true; upd; ) { > 63 upd = false; > 64 for(int a=0; a<N; ++a) > 65 for(int b=a; b<N; ++b) > 66 for(int c=0; c<N; ++c) if((1LL<<c)&dep[a][b]) { > 67 LL neo = dep[a][b] | dep[min(a,c)][max(a,c)] | d > 68 if(neo != dep[a][b]) { > 69 upd = true; > 70 dep[a][b] = neo; > 71 } > 72 } > 73 } > 74 } > 75 > 76 void add_dep(const vector<int>& a, const vector<int>& b, vector<vector<L > 77 { > 78 int N = a.size() + 1; > 79 vector<vector<int>> G(N); > 80 for(int i=0; i<N-1; ++i) { > 81 G[a[i]].push_back(b[i]); > 82 G[b[i]].push_back(a[i]); > 83 } > 84 > 85 for(int root=0; root<N; ++root) { > 86 vector<int> stk; > 87 function<void(int,int)> rec; > 88 rec = [&](int pre, int v) { > 89 stk.push_back(v); > 90 for(int mid: stk) > 91 dep[min(root,v)][max(root,v)] |= 1LL<<mi > 92 for(int u: G[v]) if(u!=pre) > 93 rec(v, u); > 94 stk.pop_back(); > 95 }; > 96 rec(-1, root); > 97 } > 98 } > 99 }; > 100 > 101 // BEGIN CUT HERE > 102 #include <ctime> > 103 double start_time; string timer() > 104 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 105 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 106 { os << "{ "; > 107 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 108 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 109 void verify_case(const int& Expected, const int& Received) { > 110 bool ok = (Expected == Received); > 111 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 112 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 113 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 114 #define END verify_case(_, DoubleTree().maximalScore(a, b, c, d, score));} > 115 int main(){ > 116 > 117 CASE(0) > 118 int a_[] = {0,0,1}; > 119 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 120 int b_[] = {1,3,2}; > 121 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 122 int c_[] = {0,0,3}; > 123 vector <int> c(c_, c_+sizeof(c_)/sizeof(*c_)); > 124 int d_[] = {1,3,2}; > 125 vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); > 126 int score_[] = {1000,24,100,-200}; > 127 vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_)); > 128 int _ = 1024; > 129 END > 130 CASE(1) > 131 int a_[] = {0,0,1}; > 132 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 133 int b_[] = {1,3,2}; > 134 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 135 int c_[] = {0,0,3}; > 136 vector <int> c(c_, c_+sizeof(c_)/sizeof(*c_)); > 137 int d_[] = {1,3,2}; > 138 vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); > 139 int score_[] = {1000,24,100,200}; > 140 vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_)); > 141 int _ = 1324; > 142 END > 143 CASE(2) > 144 int a_[] = {0,0,1}; > 145 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 146 int b_[] = {1,3,2}; > 147 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 148 int c_[] = {0,0,3}; > 149 vector <int> c(c_, c_+sizeof(c_)/sizeof(*c_)); > 150 int d_[] = {1,3,2}; > 151 vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); > 152 int score_[] = {-1000,-24,-100,-200}; > 153 vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_)); > 154 int _ = 0; > 155 END > 156 CASE(3) > 157 int a_[] = {0,0,1}; > 158 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 159 int b_[] = {1,3,2}; > 160 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 161 int c_[] = {0,0,3}; > 162 vector <int> c(c_, c_+sizeof(c_)/sizeof(*c_)); > 163 int d_[] = {1,3,2}; > 164 vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); > 165 int score_[] = {-1000,24,100,200}; > 166 vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_)); > 167 int _ = 200; > 168 END > 169 CASE(4) > 170 int a_[] = {0,0,1,1,2,2}; > 171 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 172 int b_[] = {1,2,3,4,5,6}; > 173 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 174 int c_[] = {0,0,1,1,2,2}; > 175 vector <int> c(c_, c_+sizeof(c_)/sizeof(*c_)); > 176 int d_[] = {1,2,3,4,5,6}; > 177 vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); > 178 int score_[] = {-3,2,2,-1,2,2,-1}; > 179 vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_)); > 180 int _ = 5; > 181 END > 182 CASE(5) > 183 int a_[] = {0,0,1,1,2,2}; > 184 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 185 int b_[] = {1,2,3,4,5,6}; > 186 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 187 int c_[] = {0,0,0,0,0,0}; > 188 vector <int> c(c_, c_+sizeof(c_)/sizeof(*c_)); > 189 int d_[] = {1,2,3,4,5,6}; > 190 vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); > 191 int score_[] = {-3,2,2,-1,2,2,-1}; > 192 vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_)); > 193 int _ = 5; > 194 END > 195 /* > 196 CASE(6) > 197 int a_[] = ; > 198 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 199 int b_[] = ; > 200 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 201 int c_[] = ; > 202 vector <int> c(c_, c_+sizeof(c_)/sizeof(*c_)); > 203 int d_[] = ; > 204 vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); > 205 int score_[] = ; > 206 vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_)); > 207 int _ = ; > 208 END > 209 CASE(7) > 210 int a_[] = ; > 211 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 212 int b_[] = ; > 213 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 214 int c_[] = ; > 215 vector <int> c(c_, c_+sizeof(c_)/sizeof(*c_)); > 216 int d_[] = ; > 217 vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); > 218 int score_[] = ; > 219 vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_)); > 220 int _ = ; > 221 END > 222 */ > 223 } > 224 // END CUT HERE