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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 55 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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,381,602,546,183,886,59,317,977,612,328,91,771,131}; 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 <int> foxes) 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 MaxMove) { 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.begin(), sr.second.end()); 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 118 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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,20,10,30,11,6,5,23}; 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,18,16,13,21,14,1,25}; 171 + vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 172 + int L_[] = {79374,40629,43195,73589,24200,63937,35339,7598,65109,51764,11142,84017,51078,58051,81387,22035,34883,92710,52283,57337,79309,3383,41904,35839,38242,43208,82062,24676,71838}; 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,23,47,49,50,26,40,16,10,48,25,29,15,28,46,4,20,44,17,39,32,38,2,42,8,36,3,41}; 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,13,18,9,5,1,1,26,19,50,33,50,40,29,48,50,37,16,40,48,14,30,22,47,37,7,50,6}; 182 + vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 183 + int L_[] = {22051,11109,85275,6691,43705,47374,27748,5411,62549,84079,89542,38006,82198,24083,16847,66335,3542,72495,37378,73973,85703,51682,68688,94295,31337, 184 +90071,99317,63484,43244,99079,55857,34503,79709,82140,91137,27033,91599,61168,52345,49569,58919,38133,43361, 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,49,50}; 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