Overview
| SHA1 Hash: | 10f7b8dbe60b1f9ddd04a61eb7da6a6e9f694565 |
|---|---|
| Date: | 2015-06-11 23:36:10 |
| User: | kinaba |
| Comment: | TCO15-2A |
| 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/TCO15-2A/1A.cpp version [e0fd7590ff0bfd28]
> 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 ModModMod { public: > 23 long long findSum(vector <int> m, int R) > 24 { > 25 memo.assign(m.size()+1, -1); > 26 return rec(m, 0, R); > 27 } > 28 > 29 LL rec(const vector<int>& m, int i, int R) > 30 { > 31 if(i == m.size()) > 32 return LL(1+R)*R/2; > 33 return rec_memod(m, i)*(R/m[i]) + rec(m, i+1, R%m[i]); > 34 } > 35 > 36 vector<LL> memo; > 37 LL rec_memod(const vector<int>& m, int i) { > 38 if(memo[i] >= 0) > 39 return memo[i]; > 40 return memo[i] = rec(m, i+1, m[i]-1); > 41 } > 42 }; > 43 > 44 // BEGIN CUT HERE > 45 #include <ctime> > 46 double start_time; string timer() > 47 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 48 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 49 { os << "{ "; > 50 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 51 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 52 void verify_case(const long long& Expected, const long long& Received) { > 53 bool ok = (Expected == Received); > 54 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 55 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 56 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 57 #define END verify_case(_, ModModMod().findSum(m, R));} > 58 int main(){ > 59 > 60 CASE(0) > 61 int m_[] = {5,3,2}; > 62 vector <int> m(m_, m_+sizeof(m_)/sizeof(*m_)); > 63 int R = 10; > 64 long long _ = 4LL; > 65 END > 66 CASE(1) > 67 int m_[] = {33, 15, 7, 10, 100, 9, 5}; > 68 vector <int> m(m_, m_+sizeof(m_)/sizeof(*m_)); > 69 int R = 64; > 70 long long _ = 92LL; > 71 END > 72 CASE(2) > 73 int m_[] = {995,149,28,265,275,107,555,241,702,462,519,212,362,478,783,3 > 74 vector <int> m(m_, m_+sizeof(m_)/sizeof(*m_)); > 75 int R = 992363; > 76 long long _ = 12792005LL; > 77 END > 78 CASE(3) > 79 int m_[] = {100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, > 80 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, > 81 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, > 82 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, > 83 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, > 84 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, > 85 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, > 86 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100}; > 87 vector <int> m(m_, m_+sizeof(m_)/sizeof(*m_)); > 88 int R = 100; > 89 long long _ = 4950LL; > 90 END > 91 CASE(4) > 92 int m_[] = {2934}; > 93 vector <int> m(m_, m_+sizeof(m_)/sizeof(*m_)); > 94 int R = 10000000; > 95 long long _ = 14664070144LL; > 96 END > 97 /* > 98 CASE(5) > 99 int m_[] = ; > 100 vector <int> m(m_, m_+sizeof(m_)/sizeof(*m_)); > 101 int R = ; > 102 long long _ = LL; > 103 END > 104 CASE(6) > 105 int m_[] = ; > 106 vector <int> m(m_, m_+sizeof(m_)/sizeof(*m_)); > 107 int R = ; > 108 long long _ = LL; > 109 END > 110 */ > 111 } > 112 // END CUT HERE
Added SRM/TCO15-2A/1B-U.cpp version [0d05f3c7bb207c01]
> 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 typedef int Vert; > 23 typedef int Cost; > 24 typedef pair<Cost,Vert> Edge; > 25 typedef vector<Edge> Edges; > 26 typedef vector<Edges> Graph; > 27 > 28 class FoxMeeting { public: > 29 int maxDistance(vector <int> A, vector <int> B, vector <int> L, vector < > 30 { > 31 // I hate 1-indexed numbering. > 32 for(auto& ai: A) ai--; > 33 for(auto& bi: B) bi--; > 34 for(auto& fi: foxes) fi--; > 35 > 36 const int N = A.size()+1; > 37 if(N==1) > 38 return 0; > 39 > 40 Graph G(N); > 41 for(int i=0; i<N-1; ++i) { > 42 G[A[i]].emplace_back(L[i], B[i]); > 43 G[B[i]].emplace_back(L[i], A[i]); > 44 } > 45 vector<bool> Foxed(N, false); > 46 for(int fi: foxes) > 47 Foxed[fi] = true; > 48 > 49 int best = 0x7fffffff; > 50 for(int C=0; C<N; ++C) > 51 best = min(best, solve_centered(G, C, Foxed)); > 52 return best; > 53 } > 54 > 55 int solve_centered(const Graph& G, int Root, const vector<bool>& Foxed) > 56 { > 57 int L=-1, R=5000000; // (L,R) > 58 while(R-L>1) { > 59 int C = (L+R)/2; > 60 (can(G, Root, Foxed, C) ? R : L) = C; > 61 } > 62 return R; > 63 } > 64 > 65 bool can(const Graph& G, int Root, const vector<bool>& Foxed, int MaxMov > 66 enum State {FREE, MUSTBEFILLED, BAD}; > 67 typedef pair<State, vector<Cost>> Result; > 68 function<Result(Vert,Vert)> rec; > 69 rec = [&](Vert p, Vert v)->Result { > 70 Cost parent_edge = 0; > 71 bool must_fill = false; > 72 vector<Cost> reached; > 73 for(auto& e: G[v]) > 74 if(e.second != p) { > 75 Result sr = rec(v, e.second); > 76 if(sr.first == BAD) > 77 return Result(BAD, vector<Cost>( > 78 if(sr.first == MUSTBEFILLED) > 79 must_fill = true; > 80 reached.insert(reached.end(), sr.second. > 81 } else { > 82 parent_edge = e.first; > 83 } > 84 if(Foxed[v]) > 85 reached.emplace_back(MaxMove); > 86 > 87 sort(reached.rbegin(), reached.rend()); > 88 if(must_fill) { > 89 if(reached.empty()) > 90 return Result(BAD, vector<Cost>()); > 91 reached.pop_back(); > 92 } > 93 vector<Cost> rr; > 94 for(auto& ri: reached) > 95 if(ri - parent_edge < 0) > 96 must_fill = true; > 97 else > 98 rr.push_back(ri-parent_edge); > 99 return Result(must_fill ? MUSTBEFILLED : FREE, rr); > 100 }; > 101 > 102 Result r = rec(-1, Root); > 103 return (r.first != BAD); > 104 } > 105 }; > 106 > 107 // BEGIN CUT HERE > 108 #include <ctime> > 109 double start_time; string timer() > 110 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 111 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 112 { os << "{ "; > 113 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 114 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 115 void verify_case(const int& Expected, const int& Received) { > 116 bool ok = (Expected == Received); > 117 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 118 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 119 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 120 #define END verify_case(_, FoxMeeting().maxDistance(A, B, L, foxes));} > 121 int main(){ > 122 > 123 CASE(0) > 124 int A_[] = {1}; > 125 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 126 int B_[] = {2}; > 127 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 128 int L_[] = {5}; > 129 vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); > 130 int foxes_[] = {1, 2}; > 131 vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); > 132 int _ = 0; > 133 END > 134 CASE(1) > 135 int A_[] = {1, 2}; > 136 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 137 int B_[] = {2, 3}; > 138 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 139 int L_[] = {1, 1}; > 140 vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); > 141 int foxes_[] = {1, 3}; > 142 vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); > 143 int _ = 1; > 144 END > 145 CASE(2) > 146 int A_[] = {1, 2}; > 147 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 148 int B_[] = {2, 3}; > 149 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 150 int L_[] = {1, 1}; > 151 vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); > 152 int foxes_[] = {1, 2, 3}; > 153 vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); > 154 int _ = 0; > 155 END > 156 CASE(3) > 157 int A_[] = {10,8,3,7,2,6,9,1,4}; > 158 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 159 int B_[] = {5,5,8,10,5,5,6,10,3}; > 160 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 161 int L_[] = {71846,10951,42265,37832,29439,95676,83661,28186,21216}; > 162 vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); > 163 int foxes_[] = {1,2,3,4,5,6,7,8,9,10}; > 164 vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); > 165 int _ = 0; > 166 END > 167 CASE(4) > 168 int A_[] = {8,15,22,24,2,25,13,26,18,4,9,29,1,12,3,16,14,21,19,27,17,7,2 > 169 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 170 int B_[] = {28,28,8,8,28,28,25,2,13,24,24,22,22,29,4,22,8,4,1,24,21,14,1 > 171 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 172 int L_[] = {79374,40629,43195,73589,24200,63937,35339,7598,65109,51764,1 > 173 vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); > 174 int foxes_[] = {3,5,7,9,10,14,17,19,20,21,24,25,28}; > 175 vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); > 176 int _ = 107013; > 177 END > 178 CASE(5) > 179 int A_[] = {34,14,22,9,24,19,11,37,33,21,5,30,1,43,7,31,45,27,6,12,13,35 > 180 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 181 int B_[] = {18,18,18,14,9,34,9,24,34,11,18,14,21,21,43,1,22,7,1,30,14,33 > 182 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 183 int L_[] = {22051,11109,85275,6691,43705,47374,27748,5411,62549,84079,89 > 184 90071,99317,63484,43244,99079,55857,34503,79709,82140,91137,27033,91599,61168,52 > 185 40718,2115,79278,88841,40966,42023}; > 186 vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); > 187 int foxes_[] = {5,12,13,18,23,27,28,29,32,33,34,35,36,37,40,42,43,47,48, > 188 vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); > 189 int _ = 89342; > 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 L_[] = ; > 198 vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); > 199 int foxes_[] = ; > 200 vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); > 201 int _ = ; > 202 END > 203 CASE(7) > 204 int A_[] = ; > 205 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 206 int B_[] = ; > 207 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 208 int L_[] = ; > 209 vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); > 210 int foxes_[] = ; > 211 vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); > 212 int _ = ; > 213 END > 214 */ > 215 } > 216 // END CUT HERE