Overview
| SHA1 Hash: | 6bf49a0393a3bff45a2187b053235f0e06677cc5 |
|---|---|
| Date: | 2012-12-20 15:27:42 |
| User: | kinaba |
| Comment: | 564 |
| 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/564-U/1A.cpp version [15bba962603caf18]
> 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 using namespace std; > 18 typedef long long LL; > 19 typedef long double LD; > 20 typedef complex<LD> CMP; > 21 > 22 struct UnionFind > 23 { > 24 vector<int> uf, sz; > 25 int nc; > 26 > 27 UnionFind(int N): uf(N), sz(N,1), nc(N) > 28 { for(int i=0; i<N; ++i) uf[i] = i; } > 29 int size() > 30 { return nc; } > 31 int size(int a) > 32 { return sz[Find(a)]; } > 33 int Find(int a) > 34 { return uf[a]==a ? a : uf[a]=Find(uf[a]); } > 35 bool Union(int a, int b) > 36 { > 37 a = Find(a); > 38 b = Find(b); > 39 if( a != b ) > 40 { > 41 if( sz[a] >= sz[b] ) swap(a, b); > 42 uf[a] = b; > 43 sz[b] += sz[a]; > 44 --nc; > 45 } > 46 return (a!=b); > 47 } > 48 }; > 49 > 50 class KnightCircuit2 { public: > 51 int maxSize(int w, int h) > 52 { > 53 if( w>=4 && h>=4 ) > 54 return w*h; > 55 > 56 UnionFind uf(w*h); > 57 int dy[] = {+2,+2,-2,-2,+1,+1,-1,-1}; > 58 int dx[] = {+1,-1,+1,-1,+2,-2,+2,-2}; > 59 for(int y=0; y<h; ++y) > 60 for(int x=0; x<w; ++x) > 61 for(int d=0; d<8; ++d) { > 62 int yy = y+dy[d]; > 63 int xx = x+dx[d]; > 64 if(0<=yy && yy<h && 0<=xx && xx<w) > 65 uf.Union(y*w+x, yy*w+xx); > 66 } > 67 > 68 int m = 0; > 69 for(int i=0; i<w*h; ++i) > 70 m = max(m, uf.size(i)); > 71 return m; > 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(_, KnightCircuit2().maxSize(w, h));} > 89 int main(){ > 90 > 91 CASE(0) > 92 int w = 1; > 93 int h = 1; > 94 int _ = 1; > 95 END > 96 CASE(1) > 97 int w = 15; > 98 int h = 2; > 99 int _ = 8; > 100 END > 101 CASE(2) > 102 int w = 100; > 103 int h = 100; > 104 int _ = 10000; > 105 END > 106 /* > 107 CASE(3) > 108 int w = ; > 109 int h = ; > 110 int _ = ; > 111 END > 112 CASE(4) > 113 int w = ; > 114 int h = ; > 115 int _ = ; > 116 END > 117 */ > 118 } > 119 // END CUT HERE
Added SRM/564-U/1B.cpp version [fd5e5eb809d8d0f9]
> 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 using namespace std; > 18 typedef long long LL; > 19 typedef long double LD; > 20 typedef complex<LD> CMP; > 21 > 22 class AlternateColors2 { public: > 23 long long countWays(int n, int k) > 24 { > 25 LL total = 0; > 26 for(int mini=0; mini*3<=n; ++mini) > 27 { > 28 if(mini*3 == n) { > 29 total += rgb(mini, mini, mini, k) ? 1 : 0; > 30 } else { > 31 total += rgb(mini, mini, n-mini*2, k) ? 1 : 0; > 32 total += rgb(mini, n-mini*2, mini, k) ? 1 : 0; > 33 total += rgb(n-mini*2, mini, mini, k) ? 1 : 0; > 34 int free = n - mini*3; > 35 if(free >= 2) { > 36 if(k <= mini*3) { > 37 if((k-1)%3==0) { > 38 total += (free - 1)*3; > 39 } > 40 } else { > 41 total += twoball(free, k-mini*3) > 42 } > 43 } > 44 } > 45 } > 46 return total; > 47 } > 48 > 49 bool rgb(int r, int g, int b, int k) { > 50 int mini = min(r, min(g, b)); > 51 if( k <= mini*3 ) > 52 return (k-1)%3==0; > 53 r -= mini; > 54 g -= mini; > 55 b -= mini; > 56 k -= mini*3; > 57 if(r==0) return false; > 58 if(g==0) return xx(r,b,k); > 59 if(b==0) return xx(r,g,k); > 60 } > 61 > 62 bool xx(int r, int g, int k) > 63 { > 64 int mini = min(r,g); > 65 if( k <= mini*2 ) > 66 return (k-1)%2 == 0; > 67 r -= mini; > 68 g -= mini; > 69 k -= mini*2; > 70 return r>0; > 71 } > 72 > 73 LL twoball(int n, int k) > 74 { > 75 int MM = (k-1)/2; > 76 LL total = MM; > 77 if( (MM+1)*2 <= n && (k-1)%2==0 ) > 78 total += (n-(MM+1)*2 + 1); > 79 return total; > 80 } > 81 }; > 82 > 83 // BEGIN CUT HERE > 84 #include <ctime> > 85 double start_time; string timer() > 86 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 87 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 88 { os << "{ "; > 89 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 90 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 91 void verify_case(const long long& Expected, const long long& Received) { > 92 bool ok = (Expected == Received); > 93 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 94 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 95 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 96 #define END verify_case(_, AlternateColors2().countWays(n, k));} > 97 int main(){ > 98 > 99 CASE(0) > 100 int n = 1; > 101 int k = 1; > 102 long long _ = 1LL; > 103 END > 104 CASE(1) > 105 int n = 3; > 106 int k = 3; > 107 long long _ = 3LL; > 108 END > 109 CASE(2) > 110 int n = 6; > 111 int k = 4; > 112 long long _ = 9LL; > 113 END > 114 CASE(3) > 115 int n = 6; > 116 int k = 1; > 117 long long _ = 21LL; > 118 END > 119 CASE(4) > 120 int n = 1000; > 121 int k = 2; > 122 long long _ = 1LL; > 123 END > 124 CASE(5) > 125 int n = 100000; > 126 int k = 100000; > 127 long long _ = 1666700000LL; > 128 END > 129 CASE(6) > 130 int n = 100000; > 131 int k = 100; > 132 long long _ = -1LL; > 133 END > 134 /* > 135 CASE(7) > 136 int n = ; > 137 int k = ; > 138 long long _ = LL; > 139 END > 140 */ > 141 } > 142 // END CUT HERE
Added SRM/564-U/1C-U.cpp version [e66651725115e70a]
> 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 using namespace std; > 18 typedef long long LL; > 19 typedef long double LD; > 20 typedef complex<LD> 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 class DefectiveAddition { public: > 43 int count(vector <int> cards, int n) > 44 { > 45 int n_msb = 0; > 46 while( (1<<n_msb+1) <= n ) {} > 47 > 48 vector<int> cc(30); > 49 vector<int> more; > 50 for(int i=0; i<cards.size(); ++i) { > 51 for(int k=0; k<=29; ++k) > 52 { > 53 if((1<<k)<=cards[i] && cards[i]<(1<<k+1)) > 54 cc[k].push_back(cards[i]); > 55 } > 56 } > 57 > 58 mint p = 0; > 59 for(int k=29; k>=0; --k) > 60 { > 61 int BIT = (n>>k)&1; > 62 > 63 int up = 0; > 64 > 65 vector<int> rel; > 66 for(int i=0; i<cards.size(); ++i) > 67 if( (1<<k) <= cards[i] ) { > 68 if( (1<<k+1) <= cards[i] ) > 69 up ^= cards[i]; > 70 if( (1<<k) & cards[i] ) > 71 rel.push_back(i); > 72 } > 73 > 74 // all take above > 75 if( (up>>k+1) == (n>>k+1) ) > 76 { > 77 for(int ri=0; ri<rel.size(); ++ri) > 78 { > 79 int i = rel[ri]; > 80 } > 81 } > 82 } > 83 return p.val; > 84 } > 85 }; > 86 > 87 // BEGIN CUT HERE > 88 #include <ctime> > 89 double start_time; string timer() > 90 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 91 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 92 { os << "{ "; > 93 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 94 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 95 void verify_case(const int& Expected, const int& Received) { > 96 bool ok = (Expected == Received); > 97 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 98 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 99 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 100 #define END verify_case(_, DefectiveAddition().count(cards, n));} > 101 int main(){ > 102 > 103 CASE(0) > 104 int cards_[] = {2,3}; > 105 vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); > 106 int n = 2; > 107 int _ = 3; > 108 END > 109 CASE(1) > 110 int cards_[] = {1,2,3}; > 111 vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); > 112 int n = 1; > 113 int _ = 6; > 114 END > 115 CASE(2) > 116 int cards_[] = {4, 5, 7, 11}; > 117 vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); > 118 int n = 6; > 119 int _ = 240; > 120 END > 121 CASE(3) > 122 int cards_[] = {1,2,3,4,5,6,7,8,9,10}; > 123 vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); > 124 int n = 15; > 125 int _ = 1965600; > 126 END > 127 CASE(4) > 128 int cards_[] = {1,2,3,4,5,6,7,8,9,10}; > 129 vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); > 130 int n = 16; > 131 int _ = 0; > 132 END > 133 CASE(5) > 134 int cards_[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, > 135 vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); > 136 int n = 1; > 137 int _ = 949480669; > 138 END > 139 /* > 140 CASE(6) > 141 int cards_[] = ; > 142 vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); > 143 int n = ; > 144 int _ = ; > 145 END > 146 CASE(7) > 147 int cards_[] = ; > 148 vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); > 149 int n = ; > 150 int _ = ; > 151 END > 152 */ > 153 } > 154 // END CUT HERE