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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 51 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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, vector <int> cost) 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 105 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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,22,10,14, 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,4,18,30,25, 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,122,9941,361853, 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,1000000,1000000,1000000, 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