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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 102 - cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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.