Overview
| SHA1 Hash: | 47a150c34bc92bf8141b531b0406f96aecb2ee2d |
|---|---|
| Date: | 2015-10-14 13:00:43 |
| User: | kinaba |
| Comment: | 669 |
| 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/669-U/1A-U.cpp version [d330555d42831ae2]
> 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 SubdividedSlimes { public: > 23 int needCut(int S, int M) > 24 { > 25 int L=0, R=S; > 26 while(R-L>1) { > 27 int C = (L+R)/2; > 28 (maxScore(S, C) >= M ? R : L) = C; > 29 } > 30 return R==S ? -1 : R; > 31 } > 32 > 33 LL maxScore(int S, int Turn) { > 34 LL score = 0; > 35 > 36 multiset<int, greater<int>> X; > 37 X.insert(S); > 38 for(int t=0; t<Turn && *X.begin()>1; ++t) { > 39 int V = *X.begin(), U = V/2; > 40 X.erase(X.begin()); > 41 score += U*(V-U); > 42 X.insert(U); > 43 X.insert(V-U); > 44 } > 45 return score; > 46 } > 47 }; > 48 > 49 // BEGIN CUT HERE > 50 #include <ctime> > 51 double start_time; string timer() > 52 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 53 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 54 { os << "{ "; > 55 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 56 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 57 void verify_case(const int& Expected, const int& Received) { > 58 bool ok = (Expected == Received); > 59 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 60 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 61 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 62 #define END verify_case(_, SubdividedSlimes().needCut(S, M));} > 63 int main(){ > 64 > 65 CASE(0) > 66 int S = 3; > 67 int M = 2; > 68 int _ = 1; > 69 END > 70 CASE(1) > 71 int S = 3; > 72 int M = 3; > 73 int _ = 2; > 74 END > 75 CASE(2) > 76 int S = 3; > 77 int M = 4; > 78 int _ = -1; > 79 END > 80 CASE(3) > 81 int S = 765; > 82 int M = 271828; > 83 int _ = 14; > 84 END > 85 /* > 86 CASE(4) > 87 int S = ; > 88 int M = ; > 89 int _ = ; > 90 END > 91 CASE(5) > 92 int S = ; > 93 int M = ; > 94 int _ = ; > 95 END > 96 */ > 97 } > 98 // END CUT HERE
Added SRM/669-U/1B.cpp version [1e3a19202b728a54]
> 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 mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } > 39 mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); } > 40 mint operator/(mint x, mint y) { return x/=y; } > 41 > 42 vector<mint> FAC_(1,1); > 43 mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*LL(FAC_.siz > 44 > 45 template<typename T> > 46 struct DP2 > 47 { > 48 const int N1, N2; > 49 vector<T> data; > 50 DP2(){} > 51 DP2(int N1, int N2, const T& t = T()) > 52 : N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)< > 53 T& operator()(int i1, int i2) > 54 { return data[ (i1*N2)+i2 ]; } > 55 void swap(DP2& rhs) > 56 { data.swap(rhs.data); } > 57 }; > 58 > 59 class LineMST { public: > 60 > 61 int count(int N, int L) > 62 { > 63 DP2<int> dp(N, L+1, -1); > 64 DP2<int> dp_sub(N, L+1, -1); > 65 return (solve(N-1, L, L, dp, dp_sub)*FAC(N)/2).val; > 66 } > 67 > 68 // maximum <= L > 69 mint solve(int N, int L, const int OL, DP2<int>& dp, DP2<int>& dp_sub) > 70 { > 71 if(N==0) return 1; > 72 if(L==0) return 0; > 73 if(dp(N,L) != -1) > 74 return dp(N,L); > 75 > 76 mint total = 0; > 77 for(int XL=1; XL<=L; ++XL) > 78 total += solve_sub(N, XL, OL, dp, dp_sub); > 79 return dp(N,L) = total.val; > 80 } > 81 > 82 // L = exact maximum. > 83 int solve_sub(int N, int L, const int OL, DP2<int>& dp, DP2<int>& dp_sub > 84 if(N==0) return 1; > 85 if(L==0) return 0; > 86 if(dp_sub(N,L) != -1) > 87 return dp_sub(N,L); > 88 > 89 mint total = 0; > 90 for(int maxP=1; maxP<=N; ++maxP) { > 91 total += > 92 mint(solve(maxP-1, L-1, OL, dp, dp_sub)) > 93 * solve(N-maxP, L, OL, dp, dp_sub) > 94 * POW(OL-L+1, maxP*(N-maxP+1)-1); > 95 } > 96 return dp_sub(N,L)=total.val; > 97 } > 98 }; > 99 > 100 // BEGIN CUT HERE > 101 #include <ctime> > 102 double start_time; string timer() > 103 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 104 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 105 { os << "{ "; > 106 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 107 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 108 void verify_case(const int& Expected, const int& Received) { > 109 bool ok = (Expected == Received); > 110 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 111 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 112 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 113 #define END verify_case(_, LineMST().count(N, L));} > 114 int main(){ > 115 > 116 CASE(0) > 117 int N = 3; > 118 int L = 2; > 119 int _ = 15; > 120 END > 121 CASE(1) > 122 int N = 2; > 123 int L = 10; > 124 int _ = 10; > 125 END > 126 CASE(2) > 127 int N = 3; > 128 int L = 1; > 129 int _ = 3; > 130 END > 131 CASE(3) > 132 int N = 8; > 133 int L = 41; > 134 int _ = 655468587; > 135 END > 136 CASE(4) > 137 int N = 50; > 138 int L = 50; > 139 int _ = 699887037; > 140 END > 141 CASE(4) > 142 int N = 200; > 143 int L = 200; > 144 int _ = 152699064; > 145 END > 146 /* > 147 CASE(5) > 148 int N = ; > 149 int L = ; > 150 int _ = ; > 151 END > 152 CASE(6) > 153 int N = ; > 154 int L = ; > 155 int _ = ; > 156 END > 157 */ > 158 } > 159 // END CUT HERE