Overview
| SHA1 Hash: | 1f14a4420e1a6d5ea8e38a26f0f6a343585318ab |
|---|---|
| Date: | 2015-12-01 01:54:50 |
| User: | kinaba |
| Comment: | 673-u |
| 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/673-U/1A.cpp version [4dd570b916b5bddb]
> 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 unsigned MODVAL = 1000000007; > 23 struct mint > 24 { > 25 unsigned val; > 26 mint():val(0){} > 27 mint(int x):val(x%MODVAL) {} > 28 mint(unsigned x):val(x%MODVAL) {} > 29 mint(LL x):val(x%MODVAL) {} > 30 }; > 31 mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } > 32 mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } > 33 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } > 34 mint operator+(mint x, mint y) { return x+=y; } > 35 mint operator-(mint x, mint y) { return x-=y; } > 36 mint operator*(mint x, mint y) { return x*=y; } > 37 > 38 class BearCavalry { public: > 39 int countAssignments(vector <int> warriors, vector <int> horses) > 40 { > 41 mint total = 0; > 42 > 43 const int W = warriors[0]; > 44 warriors.erase(warriors.begin()); > 45 sort(warriors.begin(), warriors.end()); > 46 sort(horses.begin(), horses.end()); > 47 > 48 for(int x=0; x<horses.size(); ++x) { > 49 const int H = horses[x]; > 50 vector<int> hs(horses.begin(), horses.begin()+x); > 51 hs.insert(hs.end(), horses.begin()+x+1, horses.end()); > 52 total += cnt(W*H, warriors, hs); > 53 } > 54 return total.val; > 55 } > 56 > 57 mint cnt(int TOP, vector<int> w, vector<int> h) > 58 { > 59 mint total = 1; > 60 for(int i=0; i<w.size(); ++i) { > 61 int W = w[w.size()-1-i]; > 62 > 63 int c=0; > 64 for(int hk: h) > 65 c += (hk*W < TOP); > 66 c -= i; > 67 if(c <= 0) > 68 return 0; > 69 total *= c; > 70 } > 71 return total; > 72 } > 73 }; > 74 > 75 // BEGIN CUT HERE > 76 #include <ctime> > 77 double start_time; string timer() > 78 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 79 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 80 { os << "{ "; > 81 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 82 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 83 void verify_case(const int& Expected, const int& Received) { > 84 bool ok = (Expected == Received); > 85 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 86 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 87 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 88 #define END verify_case(_, BearCavalry().countAssignments(warriors, horses) > 89 int main(){ > 90 > 91 CASE(0) > 92 int warriors_[] = {5,8,4,8}; > 93 vector <int> warriors(warriors_, warriors_+sizeof(warriors_)/sizeof(*w > 94 int horses_[] = {19,40,25,20}; > 95 vector <int> horses(horses_, horses_+sizeof(horses_)/sizeof(*horses_)) > 96 int _ = 2; > 97 END > 98 CASE(1) > 99 int warriors_[] = {1,1}; > 100 vector <int> warriors(warriors_, warriors_+sizeof(warriors_)/sizeof(*w > 101 int horses_[] = {1,1}; > 102 vector <int> horses(horses_, horses_+sizeof(horses_)/sizeof(*horses_)) > 103 int _ = 0; > 104 END > 105 CASE(2) > 106 int warriors_[] = {10,2,10}; > 107 vector <int> warriors(warriors_, warriors_+sizeof(warriors_)/sizeof(*w > 108 int horses_[] = {100,150,200}; > 109 vector <int> horses(horses_, horses_+sizeof(horses_)/sizeof(*horses_)) > 110 int _ = 3; > 111 END > 112 CASE(3) > 113 int warriors_[] = {10,20}; > 114 vector <int> warriors(warriors_, warriors_+sizeof(warriors_)/sizeof(*w > 115 int horses_[] = {1,3}; > 116 vector <int> horses(horses_, horses_+sizeof(horses_)/sizeof(*horses_)) > 117 int _ = 1; > 118 END > 119 CASE(4) > 120 int warriors_[] = {20,20,25,23,24,24,21}; > 121 vector <int> warriors(warriors_, warriors_+sizeof(warriors_)/sizeof(*w > 122 int horses_[] = {20,25,25,20,25,23,20}; > 123 vector <int> horses(horses_, horses_+sizeof(horses_)/sizeof(*horses_)) > 124 int _ = 0; > 125 END > 126 CASE(5) > 127 int warriors_[] = {970,800,800,800,800,800,800,800,800,800,800,800,800,8 > 128 800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800, > 129 vector <int> warriors(warriors_, warriors_+sizeof(warriors_)/sizeof(*w > 130 int horses_[] = {1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 131 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, > 132 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}; > 133 vector <int> horses(horses_, horses_+sizeof(horses_)/sizeof(*horses_)) > 134 int _ = 318608048; > 135 END > 136 /* > 137 CASE(6) > 138 int warriors_[] = ; > 139 vector <int> warriors(warriors_, warriors_+sizeof(warriors_)/sizeof(*w > 140 int horses_[] = ; > 141 vector <int> horses(horses_, horses_+sizeof(horses_)/sizeof(*horses_)) > 142 int _ = ; > 143 END > 144 CASE(7) > 145 int warriors_[] = ; > 146 vector <int> warriors(warriors_, warriors_+sizeof(warriors_)/sizeof(*w > 147 int horses_[] = ; > 148 vector <int> horses(horses_, horses_+sizeof(horses_)/sizeof(*horses_)) > 149 int _ = ; > 150 END > 151 */ > 152 } > 153 // END CUT HERE
Added SRM/673-U/1B-U.cpp version [b637a94f34ab84c4]
> 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 unsigned MODVAL = 1000000007; > 23 struct mint > 24 { > 25 unsigned val; > 26 mint():val(0){} > 27 mint(int x):val(x%MODVAL) {} > 28 mint(unsigned x):val(x%MODVAL) {} > 29 mint(LL x):val(x%MODVAL) {} > 30 }; > 31 mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } > 32 mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } > 33 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } > 34 mint operator+(mint x, mint y) { return x+=y; } > 35 mint operator-(mint x, mint y) { return x-=y; } > 36 mint operator*(mint x, mint y) { return x*=y; } > 37 > 38 vector< vector<mint> > CP_; > 39 mint C(int n, int k) { > 40 while( CP_.size() <= n ) { > 41 int nn = CP_.size(); > 42 CP_.push_back(vector<mint>(nn+1,1)); > 43 for(int kk=1; kk<nn; ++kk) > 44 CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk]; > 45 } > 46 return k<0 || n<k ? 0 : CP_[n][k]; > 47 } > 48 > 49 class BearPermutations { public: > 50 int countPermutations(int N, int S, int MOD) > 51 { > 52 MODVAL = MOD; > 53 return pat_below(N, S).val; > 54 } > 55 > 56 mint pat_below(int N, int S) { > 57 mint total = 0; > 58 for(int s=0; s<=S; ++s) > 59 total += pat_exact(N, s); > 60 return total; > 61 } > 62 > 63 vector<int> memo3; > 64 int pat_exact(int N, int S) { > 65 memo3.resize(101*101, -1); > 66 auto key = N*101+S; > 67 if(memo3[key]!=-1) > 68 return memo3[key]; > 69 > 70 mint total = 0; > 71 for(int c=0; c<N; ++c) > 72 total += pat_center_exact(N, c, S); > 73 return memo3[key] = total.val; > 74 } > 75 > 76 vector<int> memo2; > 77 int pat_exact_shifted(int N, int S, int score_offset) { > 78 memo2.resize(101*101*101, -1); > 79 auto key = (N*101+score_offset)*101+S; > 80 if(memo2[key]!=-1) > 81 return memo2[key]; > 82 > 83 mint total = 0; > 84 for(int c=0; c<N; ++c) > 85 if(score_offset+c <= S) > 86 total += pat_center_exact(N, c, S-(score_offset+ > 87 return memo2[key]=total.val; > 88 } > 89 > 90 vector<int> memo; > 91 int pat_center_exact(int N, int c, int S) > 92 { > 93 c = min(c, N-1-c); > 94 > 95 if(N==1) > 96 return (S==0 ? 1 : 0); > 97 if(c==0 || c==N-1) > 98 return pat_exact(N-1, S); > 99 > 100 memo.resize(101*101*101, -1); > 101 auto key = (N*101+c)*101+S; > 102 if(memo[key]!=-1) > 103 return memo[key]; > 104 > 105 LL total = 0; > 106 for(int cl=0; cl<c; ++cl) > 107 for(int SS=0; SS<=S; ++SS) > 108 total += ((LL)pat_center_exact(c, cl, SS) * pat_exact_sh > 109 return memo[key] = (total * C(N-1, c)).val; > 110 } > 111 }; > 112 > 113 // BEGIN CUT HERE > 114 #include <ctime> > 115 double start_time; string timer() > 116 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 117 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 118 { os << "{ "; > 119 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 120 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 121 void verify_case(const int& Expected, const int& Received) { > 122 bool ok = (Expected == Received); > 123 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 124 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 125 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 126 #define END verify_case(_, BearPermutations().countPermutations(N, S, MOD)) > 127 int main(){ > 128 > 129 CASE(0) > 130 int N = 3; > 131 int S = 1; > 132 int MOD = 71876209; > 133 int _ = 4; > 134 END > 135 CASE(1) > 136 int N = 4; > 137 int S = 0; > 138 int MOD = 1000003; > 139 int _ = 8; > 140 END > 141 CASE(2) > 142 int N = 4; > 143 int S = 1; > 144 int MOD = 483128897; > 145 int _ = 8; > 146 END > 147 CASE(3) > 148 int N = 5; > 149 int S = 3; > 150 int MOD = 907283243; > 151 int _ = 82; > 152 END > 153 CASE(4) > 154 int N = 5; > 155 int S = 100; > 156 int MOD = 101; > 157 int _ = 19; > 158 END > 159 CASE(5) > 160 int N = 20; > 161 int S = 30; > 162 int MOD = 3; > 163 int _ = 2; > 164 END > 165 CASE(6) > 166 int N = 100; > 167 int S = 100; > 168 int MOD = 1000000007; > 169 int _ = -1; > 170 END > 171 /* > 172 CASE(7) > 173 int N = ; > 174 int S = ; > 175 int MOD = ; > 176 int _ = ; > 177 END > 178 */ > 179 } > 180 // END CUT HERE