Overview
| SHA1 Hash: | 14e544f8d9268cd1093677956c169ed549ff75ff |
|---|---|
| Date: | 2011-09-28 15:32:27 |
| User: | kinaba |
| Comment: | rename |
| 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
Deleted SRM/518-U/1A.cpp version [39f7d6474ae7b753]
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 using namespace std; < 19 typedef long long LL; < 20 typedef complex<double> CMP; < 21 < 22 class LargestSubsequence { public: < 23 string getLargest(string s) < 24 { < 25 string result; < 26 for(string::iterator it=s.begin(); it!=s.end(); ) { < 27 it = max_element(it, s.end()); < 28 if( it != s.end() ) < 29 result += *it++; < 30 } < 31 return result; < 32 } < 33 }; <
Deleted SRM/518-U/1B.cpp version [3c712bb16a6c8631]
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 using namespace std; < 19 typedef long long LL; < 20 typedef complex<double> CMP; < 21 < 22 class ConvexSequence { public: < 23 long long getMinimum(vector <int> a) < 24 { < 25 int i = min_element(a.begin(), a.end()) - a.begin(); < 26 vector<LL> pre(a.begin(), a.begin()+i+1); < 27 reverse(pre.begin(), pre.end()); < 28 vector<LL> post(a.begin()+i, a.end()); < 29 return convex_incr(pre) + convex_incr(post); < 30 } < 31 < 32 LL convex_incr(vector<LL> a) < 33 { < 34 if( a.empty() ) < 35 return 0; < 36 for(int i=a.size()-1; i>=0; --i) < 37 a[i] -= a[0]; < 38 < 39 LL cnt = 0; < 40 for(int i=1; i<a.size()-1; ++i) < 41 { < 42 LL amax = a[i]; < 43 for(int k=i+1; k<a.size(); ++k) < 44 amax = min(amax, (a[k] - a[i-1]) / (k-(i-1)) + a[i-1]); < 45 if( amax < a[i] ) { < 46 cnt += a[i]-amax; < 47 a[i] = amax; < 48 } < 49 } < 50 return cnt; < 51 } < 52 }; <
Deleted SRM/518-U/1C.cpp version [1b6b6f1bf178804b]
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 <valarray> < 15 #include <stack> < 16 #include <cmath> < 17 #include <cassert> < 18 #include <cstring> < 19 using namespace std; < 20 typedef long long LL; < 21 typedef complex<double> CMP; < 22 < 23 static const int MODVAL = 1000000007; < 24 struct mint < 25 { < 26 int val; < 27 mint():val(0){} < 28 mint(int x):val(x%MODVAL) {} < 29 mint(size_t x):val(x%MODVAL) {} < 30 mint(LL x):val(x%MODVAL) {} < 31 }; < 32 mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } < 33 mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } < 34 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } < 35 mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } < 36 mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); } < 37 mint operator+(mint x, mint y) { return x+=y; } < 38 mint operator-(mint x, mint y) { return x-=y; } < 39 mint operator*(mint x, mint y) { return x*=y; } < 40 mint operator/(mint x, mint y) { return x/=y; } < 41 mint inv2 = mint(1) / 2; < 42 < 43 class Nim { public: < 44 int count(int K, int L) < 45 { < 46 valarray<mint> v(65536); < 47 v[slice(2,L-1,1)] = 1; < 48 for(unsigned p=2; p<=L; ++p) < 49 if( v[p].val ) < 50 for(unsigned q=p*p; q<=L; q+=p) < 51 v[q] = 0; < 52 < 53 pre(v, 0, 65536); < 54 valarray<mint> a(1, 65536); < 55 for(int i=1; i<=K; i<<=1, v*=v) < 56 if( K & i ) < 57 a *= v; < 58 post(a, 0, 65536); < 59 return a[0].val; < 60 } < 61 < 62 void pre(valarray<mint>& v, int s, int e) < 63 { < 64 if( s+1 == e ) < 65 return; < 66 int m = (s+e)/2; < 67 pre(v, s, m); < 68 pre(v, m, e); < 69 for(int i=s,j=m; i<m; ++i,++j) { < 70 mint vi=v[i], vj=v[j]; < 71 v[i] = vi - vj; < 72 v[j] = vi + vj; < 73 } < 74 } < 75 < 76 void post(valarray<mint>& v, int s, int e) < 77 { < 78 if( s+1 == e ) < 79 return; < 80 int m = (s+e)/2; < 81 for(int i=s,j=m; i<m; ++i,++j) { < 82 mint dif=v[i], sum=v[j]; < 83 v[i] = (sum + dif) * inv2; < 84 v[j] = (sum - dif) * inv2; < 85 } < 86 post(v, s, m); < 87 post(v, m, e); < 88 } < 89 }; < 90 < 91 // BEGIN CUT HERE < 92 #include <ctime> < 93 double start_time; string timer() < 94 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) < 95 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) < 96 { os << "{ "; < 97 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) < 98 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return < 99 void verify_case(const int& Expected, const int& Received) { < 100 bool ok = (Expected == Received); < 101 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() < 102 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' < 103 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( < 104 #define END verify_case(_, Nim().count(K, L));} < 105 int main(){ < 106 < 107 CASE(0) < 108 int K = 3; < 109 int L = 7; < 110 int _ = 6; < 111 END < 112 CASE(1) < 113 int K = 4; < 114 int L = 13; < 115 int _ = 120; < 116 END < 117 CASE(2) < 118 int K = 10; < 119 int L = 100; < 120 int _ = 294844622; < 121 END < 122 CASE(3) < 123 int K = 123456789; < 124 int L = 12345; < 125 int _ = 235511047; < 126 END < 127 CASE(4) < 128 int K = 1000000000; < 129 int L = 50000; < 130 int _ = 428193537; < 131 END < 132 /* < 133 CASE(5) < 134 int K = ; < 135 int L = ; < 136 int _ = ; < 137 END < 138 */ < 139 } < 140 // END CUT HERE <
Name change from from SRM/518-U/1A.cpp to SRM/518/1A.cpp.
Name change from from SRM/518-U/1B.cpp to SRM/518/1B.cpp.
Name change from from SRM/518-U/1C.cpp to SRM/518/1C.cpp.