Overview
| SHA1 Hash: | 982758e5e41f1573827fcd63a0dbd4bc8eeb60fa |
|---|---|
| Date: | 2011-11-29 09:59:12 |
| User: | kinaba |
| Comment: | 524 |
| 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/524-U/1A.cpp version [d971d0647e4bd58e]
> 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 MagicDiamonds { public: > 29 long long minimalTransfer(long long n) > 30 { > 31 if( n <= 3 ) > 32 return n; > 33 for(LL p=2; p*p<=n && p<n; ++p) > 34 if( n%p == 0 ) > 35 return 1; > 36 return 2; > 37 } > 38 }; > 39 > 40 // BEGIN CUT HERE > 41 #include <ctime> > 42 double start_time; string timer() > 43 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 44 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 45 { os << "{ "; > 46 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 47 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 48 void verify_case(const long long& Expected, const long long& Received) { > 49 bool ok = (Expected == Received); > 50 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 51 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 52 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 53 #define END verify_case(_, MagicDiamonds().minimalTransfer(n));} > 54 int main(){ > 55 > 56 CASE(0) > 57 long long n = 2LL; > 58 long long _ = 2LL; > 59 END > 60 CASE(1) > 61 long long n = 4294967297LL; > 62 long long _ = 1LL; > 63 END > 64 CASE(2) > 65 long long n = 2147483647LL; > 66 long long _ = 2LL; > 67 END > 68 CASE(3) > 69 long long n = 1LL; > 70 long long _ = 1LL; > 71 END > 72 CASE(4) > 73 long long n = 1000000000000LL; > 74 long long _ = -1LL; > 75 END > 76 /* > 77 CASE(5) > 78 long long n = LL; > 79 long long _ = LL; > 80 END > 81 */ > 82 } > 83 // END CUT HERE
Added SRM/524-U/1B.cpp version [38ff0d11552da11a]
> 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 LongestSequence { public: > 29 int maxLength(vector <int> C) > 30 { > 31 vector<int> P, N; > 32 for(int i=0; i<C.size(); ++i) > 33 if( C[i]<0 ) > 34 N.push_back(-C[i]); > 35 else > 36 P.push_back(+C[i]); > 37 sort(P.begin(), P.end()); > 38 sort(N.begin(), N.end()); > 39 if( P.empty() || N.empty() ) > 40 return -1; > 41 > 42 int L = 0, R = 10000000; > 43 while( R-L > 1 ) { > 44 int C = (L+R)/2; > 45 (has_loop(N, P, C) ? R : L) = C; > 46 } > 47 return L; > 48 } > 49 > 50 bool has_loop(const vector<int>& N, const vector<int>& P, int MAX) > 51 { > 52 vector<bool> vis(MAX+1, false); > 53 queue<int> Q; > 54 Q.push(0); > 55 vis[0] = true; > 56 while( !Q.empty() ) { > 57 int v = Q.front(); > 58 Q.pop(); > 59 for(int i=0; i<N.size(); ++i) > 60 if( v - N[i] == 0 ) > 61 return true; > 62 else if( v-N[i] > 0 && !vis[v-N[i]] ) > 63 {vis[v-N[i]]=true; Q.push(v-N[i]);} > 64 for(int i=0; i<P.size(); ++i) > 65 if( v+P[i] <= MAX && !vis[v+P[i]] ) > 66 {vis[v+P[i]]=true; Q.push(v+P[i]);} > 67 } > 68 return false; > 69 } > 70 }; > 71 > 72 // BEGIN CUT HERE > 73 #include <ctime> > 74 double start_time; string timer() > 75 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 76 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 77 { os << "{ "; > 78 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 79 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 80 void verify_case(const int& Expected, const int& Received) { > 81 bool ok = (Expected == Received); > 82 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 83 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 84 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 85 #define END verify_case(_, LongestSequence().maxLength(C));} > 86 int main(){ > 87 > 88 CASE(0) > 89 int C_[] = {-2,3}; > 90 vector <int> C(C_, C_+sizeof(C_)/sizeof(*C_)); > 91 int _ = 3; > 92 END > 93 CASE(1) > 94 int C_[] = {524}; > 95 vector <int> C(C_, C_+sizeof(C_)/sizeof(*C_)); > 96 int _ = -1; > 97 END > 98 CASE(2) > 99 int C_[] = {1, -1}; > 100 vector <int> C(C_, C_+sizeof(C_)/sizeof(*C_)); > 101 int _ = 0; > 102 END > 103 CASE(3) > 104 int C_[] = {11,-7}; > 105 vector <int> C(C_, C_+sizeof(C_)/sizeof(*C_)); > 106 int _ = 16; > 107 END > 108 CASE(4) > 109 int C_[] = {-227,690,590,-524}; > 110 vector <int> C(C_, C_+sizeof(C_)/sizeof(*C_)); > 111 int _ = 713; > 112 END > 113 CASE(5) > 114 int C_[] = {273,752,-738,-34,863,-21,-532,-824,-170,-130,206,346,836,149 > 115 vector <int> C(C_, C_+sizeof(C_)/sizeof(*C_)); > 116 int _ = -1; > 117 END > 118 CASE(6) > 119 int C_[] = {3,4,3,3,1,4,4,-5,3,1,5,5,3,2,-1,-5,-4,2,-4,2,-2,-2,1,-5,4,-3 > 120 vector <int> C(C_, C_+sizeof(C_)/sizeof(*C_)); > 121 int _ = -1; > 122 END > 123 > 124 } > 125 // END CUT-1000 HERE
Added SRM/524-U/1C-U.cpp version [f38a8ea9a6bc4e27]
> 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 = 1000000009; // 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 > 50 class AxonometricProjection { public: > 51 int howManyWays(vector <int> left, vector <int> front) > 52 { > 53 mint ans = 1; > 54 sort(left.begin(), left.end()); > 55 sort(front.begin(), front.end()); > 56 ans *= perm(left); > 57 ans *= perm(front); > 58 for(int i=0, k=0; i<left.size() || k<front.size(); ) > 59 { > 60 if( k<front.size() && (i==left.size() || front[k]<left[i > 61 { > 62 // advance k > 63 int h = front[k]; > 64 int len = 0; > 65 while( k!=front.size() && front[k]==h ) > 66 ++k, ++len; > 67 ans *= choose(h, len); > 68 } > 69 else if( i<left.size() && (k==front.size() || left[i]<fr > 70 { > 71 // advance i > 72 int h = left[i]; > 73 int len = 0; > 74 while( i!=left.size() && left[i]==h ) > 75 ++i, ++len; > 76 ans *= choose(h, len); > 77 } > 78 else > 79 { > 80 // both > 81 int h = left[i]; > 82 assert( h == front[k] ); > 83 int len1 = 0, len2 = 0; > 84 while( i!=left.size() && left[i]==h ) > 85 ++i, ++len1; > 86 while( k!=front.size() && front[k]==h ) > 87 ++k, ++len2; > 88 ans *= choose2(h, len1, len2); > 89 } > 90 } > 91 return ans.val; > 92 } > 93 > 94 mint perm(const vector<int>& x) > 95 { > 96 map<int,int> cat; > 97 for(int i=0; i<x.size(); ++i) > 98 cat[x[i]]++; > 99 mint r = FAC(x.size()); > 100 for(map<int,int>::iterator it=cat.begin(); it!=cat.end(); ++it) > 101 r /= FAC(it->second); > 102 return r; > 103 } > 104 > 105 mint choose(int h, int n) > 106 { > 107 mint r = 0; > 108 for(int k=1; k<=n; ++k) > 109 r += C(n, k) * POW(h, n-k); > 110 return r; > 111 } > 112 > 113 mint choose2(int h, int n1, int n2) > 114 { > 115 return POW(2, n1+n2) + h * choose(h,n1) * choose(h,n2); > 116 } > 117 }; > 118 > 119 // BEGIN CUT HERE > 120 #include <ctime> > 121 double start_time; string timer() > 122 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 123 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 124 { os << "{ "; > 125 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 126 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 127 void verify_case(const int& Expected, const int& Received) { > 128 bool ok = (Expected == Received); > 129 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 130 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 131 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 132 #define END verify_case(_, AxonometricProjection().howManyWays(heightsOfLef > 133 int main(){ > 134 > 135 CASE(0) > 136 int heightsOfLeftView_[] = {1,1}; > 137 vector <int> heightsOfLeftView(heightsOfLeftView_, heightsOfLeftView_+ > 138 int heightsOfFrontView_[] = {1,1}; > 139 vector <int> heightsOfFrontView(heightsOfFrontView_, heightsOfFrontVie > 140 int _ = 7; > 141 END > 142 CASE(1) > 143 int heightsOfLeftView_[] = {50,50,50,50,524}; > 144 vector <int> heightsOfLeftView(heightsOfLeftView_, heightsOfLeftView_+ > 145 int heightsOfFrontView_[] = {524,524}; > 146 vector <int> heightsOfFrontView(heightsOfFrontView_, heightsOfFrontVie > 147 int _ = 104060401; > 148 END > 149 CASE(2) > 150 int heightsOfLeftView_[] = {1,2,3,4,5,6,7,8,9,10}; > 151 vector <int> heightsOfLeftView(heightsOfLeftView_, heightsOfLeftView_+ > 152 int heightsOfFrontView_[] = {1,2,3,4,5,6,7,8,9,10,11}; > 153 vector <int> heightsOfFrontView(heightsOfFrontView_, heightsOfFrontVie > 154 int _ = 0; > 155 END > 156 CASE(3) > 157 int heightsOfLeftView_[] = {5,2,4,1}; > 158 vector <int> heightsOfLeftView(heightsOfLeftView_, heightsOfLeftView_+ > 159 int heightsOfFrontView_[] = {5,2,4,0,1}; > 160 vector <int> heightsOfFrontView(heightsOfFrontView_, heightsOfFrontVie > 161 int _ = 429287; > 162 END > 163 CASE(4) > 164 int heightsOfLeftView_[] = {5,2,4,52,24,524}; > 165 vector <int> heightsOfLeftView(heightsOfLeftView_, heightsOfLeftView_+ > 166 int heightsOfFrontView_[] = {0,4,20,24,500,504,520,524}; > 167 vector <int> heightsOfFrontView(heightsOfFrontView_, heightsOfFrontVie > 168 int _ = 97065655; > 169 END > 170 /* > 171 CASE(5) > 172 int heightsOfLeftView_[] = ; > 173 vector <int> heightsOfLeftView(heightsOfLeftView_, heightsOfLeftView_+ > 174 int heightsOfFrontView_[] = ; > 175 vector <int> heightsOfFrontView(heightsOfFrontView_, heightsOfFrontVie > 176 int _ = ; > 177 END > 178 CASE(6) > 179 int heightsOfLeftView_[] = ; > 180 vector <int> heightsOfLeftView(heightsOfLeftView_, heightsOfLeftView_+ > 181 int heightsOfFrontView_[] = ; > 182 vector <int> heightsOfFrontView(heightsOfFrontView_, heightsOfFrontVie > 183 int _ = ; > 184 END > 185 */ > 186 } > 187 // END CUT HERE