Overview
| SHA1 Hash: | 1fbde9e2e268b70149107301defcf8ef0f163178 |
|---|---|
| Date: | 2012-02-09 15:21:11 |
| User: | kinaba |
| Comment: | 531 |
| 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/530-U/2A.cpp version [de20996497f56abf]
> 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 <cstring> > 18 #ifdef __GNUC__ > 19 #include <ext/hash_map> > 20 #define unordered_map __gnu_cxx::hash_map > 21 #else > 22 #include <unordered_map> > 23 #endif > 24 using namespace std; > 25 typedef long long LL; > 26 typedef complex<double> CMP; > 27 > 28 class GogoXBallsAndBinsEasy { public: > 29 int solve(vector <int> T) > 30 { > 31 int maxMove = 0; > 32 > 33 vector<int> S = T; > 34 > 35 reverse(S.begin(), S.end()); > 36 int dif = 0; > 37 for(int i=0; i<S.size(); ++i) > 38 dif += abs(S[i]-T[i]); > 39 maxMove = max(maxMove, dif/2); > 40 /* > 41 sort(S.begin(), S.end()); > 42 do { > 43 int dif = 0; > 44 for(int i=0; i<S.size(); ++i) > 45 dif += abs(S[i]-T[i]); > 46 maxMove = max(maxMove, dif/2); > 47 } while( next_permutation(S.begin(), S.end()) ); > 48 */ > 49 return maxMove; > 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(_, GogoXBallsAndBinsEasy().solve(T));} > 67 int main(){ > 68 > 69 CASE(0) > 70 int T_[] = {0, 2, 5}; > 71 vector <int> T(T_, T_+sizeof(T_)/sizeof(*T_)); > 72 int _ = 5; > 73 END > 74 CASE(1) > 75 int T_[] = {5, 6, 7, 8}; > 76 vector <int> T(T_, T_+sizeof(T_)/sizeof(*T_)); > 77 int _ = 4; > 78 END > 79 CASE(2) > 80 int T_[] = {0, 1, 2, 10}; > 81 vector <int> T(T_, T_+sizeof(T_)/sizeof(*T_)); > 82 int _ = 11; > 83 END > 84 CASE(3) > 85 int T_[] = {1, 2, 3, 4, 5, 6, 7, 8}; > 86 vector <int> T(T_, T_+sizeof(T_)/sizeof(*T_)); > 87 int _ = 16; > 88 END > 89 /* > 90 CASE(4) > 91 int T_[] = ; > 92 vector <int> T(T_, T_+sizeof(T_)/sizeof(*T_)); > 93 int _ = ; > 94 END > 95 CASE(5) > 96 int T_[] = ; > 97 vector <int> T(T_, T_+sizeof(T_)/sizeof(*T_)); > 98 int _ = ; > 99 END > 100 */ > 101 } > 102 // END CUT HERE
Added SRM/531-U/1A.cpp version [7c1da83b0a1da4da]
> 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 <cstring> > 18 #ifdef __GNUC__ > 19 #include <ext/hash_map> > 20 #define unordered_map __gnu_cxx::hash_map > 21 #else > 22 #include <unordered_map> > 23 #endif > 24 using namespace std; > 25 typedef long long LL; > 26 typedef complex<double> CMP; > 27 > 28 static const int MODVAL = 1000000007; // must be prime for op/ > 29 struct mint > 30 { > 31 int val; > 32 mint():val(0){} > 33 mint(int x):val(x%MODVAL) {} // x>=0 > 34 mint(size_t x):val(x%MODVAL) {} // x>=0 > 35 mint(LL x):val(x%MODVAL) {} // x>=0 > 36 }; > 37 mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } > 38 mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } > 39 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } > 40 mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } > 41 mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); } > 42 mint operator+(mint x, mint y) { return x+=y; } > 43 mint operator-(mint x, mint y) { return x-=y; } > 44 mint operator*(mint x, mint y) { return x*=y; } > 45 mint operator/(mint x, mint y) { return x/=y; } > 46 vector<mint> FAC_(1,1); > 47 mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() > 48 mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); } > 49 mint Perm(LL n, LL k) { return FAC(n) / FAC(n-k); } > 50 > 51 class NoRepeatPlaylist { public: > 52 int numPlaylists(int N, int M, int P) > 53 { > 54 if( N == P ) > 55 return FAC(N).val; > 56 > 57 if( M == N ) > 58 return 0; > 59 > 60 int r = M+1; > 61 vector<mint> heard(N+1, 0); > 62 heard[r] = Perm(N, r); > 63 for(int i=0; i<P-r; ++i) { > 64 vector<mint> h2(N+1, 0); > 65 for(int x=0; x<=N; ++x) { > 66 if(x>=M) > 67 h2[x] += heard[x] * (x-M); > 68 if(x<N) > 69 h2[x+1] += heard[x] * (N - x); > 70 } > 71 heard = h2; > 72 } > 73 return heard[N].val; > 74 } > 75 }; > 76 > 77 // BEGIN CUT HERE > 78 #include <ctime> > 79 double start_time; string timer() > 80 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 81 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 82 { os << "{ "; > 83 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 84 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 85 void verify_case(const int& Expected, const int& Received) { > 86 bool ok = (Expected == Received); > 87 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 88 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 89 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 90 #define END verify_case(_, NoRepeatPlaylist().numPlaylists(N, M, P));} > 91 int main(){ > 92 > 93 CASE(0) > 94 int N = 1; > 95 int M = 0; > 96 int P = 3; > 97 int _ = 1; > 98 END > 99 CASE(1) > 100 int N = 1; > 101 int M = 1; > 102 int P = 3; > 103 int _ = 0; > 104 END > 105 CASE(2) > 106 int N = 2; > 107 int M = 0; > 108 int P = 3; > 109 int _ = 6; > 110 END > 111 CASE(3) > 112 int N = 4; > 113 int M = 0; > 114 int P = 4; > 115 int _ = 24; > 116 END > 117 CASE(4) > 118 int N = 2; > 119 int M = 1; > 120 int P = 4; > 121 int _ = 2; > 122 END > 123 CASE(5) > 124 int N = 50; > 125 int M = 5; > 126 int P = 100; > 127 int _ = 222288991; > 128 END > 129 /* > 130 CASE(6) > 131 int N = ; > 132 int M = ; > 133 int P = ; > 134 int _ = ; > 135 END > 136 CASE(7) > 137 int N = ; > 138 int M = ; > 139 int P = ; > 140 int _ = ; > 141 END > 142 */ > 143 } > 144 // END CUT HERE