Overview
| SHA1 Hash: | d171a2e25ccfd5fc4a5634a4a2892b6dafb4d41e |
|---|---|
| Date: | 2015-03-17 10:17:50 |
| User: | kinaba |
| Comment: | 651 |
| 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/651-U/1A.cpp version [8b0a50db0b0c12c6]
> 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 static const int MODVAL = 1000000007; > 23 class ThePermutationGame { public: > 24 int findMin(int N) > 25 { > 26 LL ans = 1; > 27 > 28 vector<bool> isp(N+1, true); > 29 for(int p=2; p<=N; ++p) > 30 if( isp[p] ) { > 31 for(int q=p+p; q<=N; q+=p) > 32 isp[q] = false; > 33 for(int v=p; v<=N; v*=p) > 34 ans = (ans*p) % MODVAL; > 35 } > 36 return int(ans); > 37 } > 38 }; > 39 > 40 // BEGIN CUT HERE > 41 #include <ctime> > 42 double start_time; string timer() > 43 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 44 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 45 { os << "{ "; > 46 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 47 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 48 void verify_case(const int& Expected, const int& Received) { > 49 bool ok = (Expected == Received); > 50 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 51 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 52 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 53 #define END verify_case(_, ThePermutationGame().findMin(N));} > 54 int main(){ > 55 > 56 CASE(0) > 57 int N = 2; > 58 int _ = 2; > 59 END > 60 CASE(1) > 61 int N = 3; > 62 int _ = 6; > 63 END > 64 CASE(2) > 65 int N = 11; > 66 int _ = 504; > 67 END > 68 CASE(3) > 69 int N = 102; > 70 int _ = 841777601; > 71 END > 72 CASE(4) > 73 int N = 9999; > 74 int _ = 804862568; > 75 END > 76 /* > 77 CASE(5) > 78 int N = ; > 79 int _ = ; > 80 END > 81 CASE(6) > 82 int N = ; > 83 int _ = ; > 84 END > 85 */ > 86 } > 87 // END CUT HERE
Added SRM/651-U/1B-U.cpp version [8cc09a515372166f]
> 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 LL Cost; > 24 typedef pair<Cost,Vert> edge; > 25 typedef vector<edge> edges; > 26 typedef vector<edges> graph; > 27 const LL INF = 0x3ffffffffffff; > 28 > 29 class MaliciousPath { public: > 30 long long minPath(int N, int K, vector <int> from, vector <int> to, vect > 31 { > 32 graph G(N), Gr(N); > 33 for(int i=0; i<from.size(); ++i) { > 34 G[from[i]].emplace_back(cost[i], to[i]); > 35 Gr[to[i]].emplace_back(cost[i], from[i]); > 36 } > 37 > 38 vector<Cost> d(N, INF); { > 39 priority_queue<edge, edges, greater<edge>> Q; > 40 Q.emplace(0, N-1); > 41 while(!Q.empty()) { > 42 Cost c = Q.top().first; > 43 Vert v = Q.top().second; > 44 Q.pop(); > 45 if(d[v] <= c) > 46 continue; > 47 d[v] = c; > 48 for(auto e: Gr[v]) { > 49 Cost cc = c + e.first; > 50 Vert vv = e.second; > 51 if(d[vv] == INF) > 52 Q.emplace(cc, vv); > 53 } > 54 } > 55 if(d[0] == INF) > 56 return -1; > 57 } > 58 > 59 while(K --> 0) { > 60 vector<Cost> d2(N, 0); > 61 for(Vert v=0; v<N-1; ++v) { > 62 LL worst = 0; > 63 for(auto e: G[v]) > 64 worst = max(worst, e.first+d[e.second]); > 65 d2[v] = worst; > 66 } > 67 > 68 d.assign(N, INF); > 69 > 70 priority_queue<edge, edges, greater<edge>> Q; > 71 Q.emplace(0, N-1); > 72 while(!Q.empty()) { > 73 Cost c = Q.top().first; > 74 Vert v = Q.top().second; > 75 Q.pop(); > 76 if(d[v] <= c) > 77 continue; > 78 if(c < d2[v]) > 79 continue; > 80 d[v] = c; > 81 for(auto e: Gr[v]) { > 82 Vert vv = e.second; > 83 Cost cc = max(d2[vv], c + e.first); > 84 if(d[vv] == INF) > 85 Q.emplace(cc, vv); > 86 } > 87 } > 88 } > 89 > 90 return d[0]; > 91 } > 92 }; > 93 > 94 // BEGIN CUT HERE > 95 #include <ctime> > 96 double start_time; string timer() > 97 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 98 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 99 { os << "{ "; > 100 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 101 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 102 void verify_case(const long long& Expected, const long long& Received) { > 103 bool ok = (Expected == Received); > 104 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 105 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 106 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 107 #define END verify_case(_, MaliciousPath().minPath(N, K, from, to, cost));} > 108 int main(){ > 109 > 110 CASE(0) > 111 int N = 3; > 112 int K = 1000; > 113 int from_[] = {0,1,1,2}; > 114 vector <int> from(from_, from_+sizeof(from_)/sizeof(*from_)); > 115 int to_[] = {1,0,2,2}; > 116 vector <int> to(to_, to_+sizeof(to_)/sizeof(*to_)); > 117 int cost_[] = {3,2,1,1}; > 118 vector <int> cost(cost_, cost_+sizeof(cost_)/sizeof(*cost_)); > 119 long long _ = 5004LL; > 120 END > 121 CASE(1) > 122 int N = 4; > 123 int K = 1; > 124 int from_[] = {0,0,1,1,1,2,2,3}; > 125 vector <int> from(from_, from_+sizeof(from_)/sizeof(*from_)); > 126 int to_[] = {1,3,0,2,3,2,1,3}; > 127 vector <int> to(to_, to_+sizeof(to_)/sizeof(*to_)); > 128 int cost_[] = {0,100,103,0,0,34,102,33}; > 129 vector <int> cost(cost_, cost_+sizeof(cost_)/sizeof(*cost_)); > 130 long long _ = 100LL; > 131 END > 132 CASE(2) > 133 int N = 10; > 134 int K = 5; > 135 int from_[] = {0,0,1,1,2,2,3,3,4,4,4,5,5,6,6,7,7,8,8,9,9}; > 136 vector <int> from(from_, from_+sizeof(from_)/sizeof(*from_)); > 137 int to_[] = {1,1,2,2,3,3,4,4,5,5,4,6,6,7,7,8,8,9,9,9,9}; > 138 vector <int> to(to_, to_+sizeof(to_)/sizeof(*to_)); > 139 int cost_[] = {2,10,10,1,2,10,10,1,2,10,100,10,2,1,10,10,2,1,10,10,1}; > 140 vector <int> cost(cost_, cost_+sizeof(cost_)/sizeof(*cost_)); > 141 long long _ = 514LL; > 142 END > 143 CASE(3) > 144 int N = 50; > 145 int K = 200; > 146 int from_[] = {0,13,8,17,3,8,4,21,11,20,2,18,21,2,4,9,17,0,14,10,15,18,1 > 147 19,24,5,5,12,7,7,16,19,13,20,15,23,6,23,9,3,6,16,11,22,24,12,1,25,25, > 148 26,26,27,27,28,28,29,29,30,30,31,31,32,32,33,33,34,34,35,35,36,36,37, > 149 37,38,38,39,39,40,40,41,41,42,42,43,43,44,44,45,45,46,46,47,47,48,48, > 150 49,49,37,9,14,0,33,20,46,26,12,11,2,7,34,19,37,5,2,17,41,16,34,13,18, > 151 35,6,14,16,25,9,10,5,10,7,36,45,3,6,22,32,28,45,40,16,36,28,16,34,1, > 152 9,19,18,6,15,29,12,5,44,33,49,14,40,1,30,21,37,49,1,44,42,6,38,1,31, > 153 40,37,34,35,6,43,29,41,48,17,4,38,26,4,46,43,6,27,30,0,16,40,33,0,42, > 154 41,10,33,47,11,37,49,25,36,20,47,12,28,17,11,17,26,26,37,34,27,17,8, > 155 2,13,43,36,28,1,23,29,40,18,22,0,7,30,23,3,39,5,23,28,38,44,19,43,15, > 156 16,43,5,27,24,25,7,16,38,33,33,1,9,25,47,0,31,30,29,4,36,49,26,6,39, > 157 40,28,39,48,26,2,15,41,42,32,0,35,34,28,30,40,3,33,16,15,41,45,12,33, > 158 35,16,47,34,23}; > 159 vector <int> from(from_, from_+sizeof(from_)/sizeof(*from_)); > 160 int to_[] = {41,42,17,0,2,7,28,32,31,33,6,42,11,13,7,40,47,21,4,6,19,15, > 161 2,10,30,34,1,47,35,23,3,0,9,25,42,21,4,6,47,32,5,40,5,0,8,49,16,29,8, > 162 11,42,33,35,26,27,43,35,6,14,13,44,25,13,42,2,26,17,3,40,31,18,12,24, > 163 37,0,37,15,44,35,40,10,1,35,47,36,33,2,39,23,28,32,0,6,21,33,41,0,19, > 164 16,29,35,16,44,6,18,17,2,46,41,11,27,5,44,1,48,15,43,8,41,33,16,11,45, > 165 47,19,41,14,41,8,24,13,3,44,41,42,30,31,44,21,14,43,48,0,6,25,38,36,14, > 166 36,22,43,15,20,19,37,25,17,44,17,46,8,25,33,19,42,40,42,24,15,31,34,8, > 167 41,25,20,29,2,5,43,28,33,40,31,27,6,21,9,35,8,8,26,13,11,31,4,4,30,34, > 168 35,1,15,11,10,24,15,24,23,16,24,32,9,1,6,17,48,6,35,19,12,5,21,23,25,9, > 169 17,47,19,23,22,35,19,5,1,10,9,41,11,45,0,23,0,11,39,0,17,2,18,4,17,24,0, > 170 10,19,4,36,22,42,18,13,48,27,11,19,28,31,39,32,48,2,26,38,43,38,49,34, > 171 37,11,9,11,14,12,9,37,0,22,14,15,0,8,23,7,43,5,8,16,47}; > 172 vector <int> to(to_, to_+sizeof(to_)/sizeof(*to_)); > 173 int cost_[] = {494,848305,3326,6008,223,2,6,673,152335,25,713909,42842,1 > 174 35,20157,1098,41,83693,365851,43843,622,591230,7722,2489,7,861622,21272, > 175 169,1153,3,7,3,577031,24522,5,241,757900,11036,8892,199,7,2,1,453031,115, > 176 13,125,67,35,91,33427,14,106,203749,5,1804,4543,23,1,281,441212,18,3, > 177 11629,233,388188,10,701,76170,763,875,11606,44972,6449,37409,83516,5912, > 178 6,705899,26759,253,580531,14215,21916,884775,30,678,5940,17,480830,8, > 179 61,218613,683352,4,557589,2619,3658,221515,15825,163577,25,9,1,4,13,2,88, > 180 147,110163,18118,2,15429,211872,24,1,188382,12500,2348,190,4279,40,8428, > 181 56325,933152,231523,9454,21,4855,96168,1722,329515,77,1,3,3518,10926, > 182 12172,4,71,181976,1318,9,5086,905,108490,80164,2,10236,197,1880,17420, > 183 614650,372457,13918,36,17,167,6,254127,512,15,341436,1,186,96,7,3,42,4, > 184 3,4,492598,18523,172302,1,421535,390382,2952,6228,871,505372,131266,5, > 185 743902,11,34,657,4717,3196,259,192504,229,6786,28,44364,21123,8,166781, > 186 885021,2,828,497,376,24707,52,1,1659,19402,27261,82,473,443,1089,586,20, > 187 7,239277,27132,4681,761,10644,17798,1,820306,13330,19,293167,2,4,89279, > 188 14,1,9,18023,1165,495221,32304,538,178613,1,4764,32767,114,103,1,302,428, > 189 92,927352,22270,2646,3599,6,16362,3,4,280286,338,652,2,347022,23,323084, > 190 3338,46,58,1263,93,46992,19112,1,19499,33,807600,20296,16803,911294,3151, > 191 1,793,1,1,504,62209,1397,52726,3650,54,3630,358480,178,394,28,137436,52764, > 192 1209,1599}; > 193 vector <int> cost(cost_, cost_+sizeof(cost_)/sizeof(*cost_)); > 194 long long _ = 121213509LL; > 195 END > 196 CASE(4) > 197 int N = 20; > 198 int K = 1000; > 199 int from_[] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,18}; > 200 vector <int> from(from_, from_+sizeof(from_)/sizeof(*from_)); > 201 int to_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,0,0}; > 202 vector <int> to(to_, to_+sizeof(to_)/sizeof(*to_)); > 203 int cost_[] = {1000000,1000000,1000000,1000000,1000000,1000000,1000000,1 > 204 1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000, > 205 1000000}; > 206 vector <int> cost(cost_, cost_+sizeof(cost_)/sizeof(*cost_)); > 207 long long _ = 19019000000LL; > 208 END > 209 CASE(5) > 210 int N = 2; > 211 int K = 0; > 212 int from_[] = {0,1}; > 213 vector <int> from(from_, from_+sizeof(from_)/sizeof(*from_)); > 214 int to_[] = {0,1}; > 215 vector <int> to(to_, to_+sizeof(to_)/sizeof(*to_)); > 216 int cost_[] = {5,4}; > 217 vector <int> cost(cost_, cost_+sizeof(cost_)/sizeof(*cost_)); > 218 long long _ = -1LL; > 219 END > 220 /* > 221 CASE(6) > 222 int N = ; > 223 int K = ; > 224 int from_[] = ; > 225 vector <int> from(from_, from_+sizeof(from_)/sizeof(*from_)); > 226 int to_[] = ; > 227 vector <int> to(to_, to_+sizeof(to_)/sizeof(*to_)); > 228 int cost_[] = ; > 229 vector <int> cost(cost_, cost_+sizeof(cost_)/sizeof(*cost_)); > 230 long long _ = LL; > 231 END > 232 CASE(7) > 233 int N = ; > 234 int K = ; > 235 int from_[] = ; > 236 vector <int> from(from_, from_+sizeof(from_)/sizeof(*from_)); > 237 int to_[] = ; > 238 vector <int> to(to_, to_+sizeof(to_)/sizeof(*to_)); > 239 int cost_[] = ; > 240 vector <int> cost(cost_, cost_+sizeof(cost_)/sizeof(*cost_)); > 241 long long _ = LL; > 242 END > 243 */ > 244 } > 245 // END CUT HERE