Overview
| SHA1 Hash: | e3362a9488bd08cbe6085633b4f0cceca8f1a3a2 |
|---|---|
| Date: | 2014-05-10 14:58:59 |
| User: | kinaba |
| Comment: | 619 |
| 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/619-U/1A.cpp version [c3cddc4fcc7fde59]
> 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 Family { public: > 23 string isFamily(vector <int> parent1, vector <int> parent2) > 24 { > 25 return solve(parent1, parent2) ? "Possible" : "Impossible"; > 26 } > 27 > 28 bool solve(vector <int> parent1, vector <int> parent2) > 29 { > 30 const int N = parent1.size(); > 31 > 32 map<int, vector<int>> diff; > 33 for(int i=0; i<N; ++i) > 34 { > 35 int a = parent1[i]; > 36 int b = parent2[i]; > 37 if(a != -1) { > 38 assert(b != -1); > 39 diff[a].push_back(b); > 40 diff[b].push_back(a); > 41 } > 42 } > 43 > 44 bool ok = true; > 45 > 46 enum {Unk, Ma=1, Fe=2}; > 47 vector<int> gender(N, Unk); > 48 function<void(int)> rec_fill; rec_fill = [&](int p) { > 49 for(int q : diff[p]) > 50 if(gender[q] == Unk) { > 51 gender[q] = 3 - gender[p]; > 52 rec_fill(q); > 53 } else if(gender[q] == gender[p]) { > 54 ok = false; > 55 return; > 56 } > 57 }; > 58 > 59 for(int p=0; p<N; ++p) > 60 { > 61 if(gender[p] == Unk) { > 62 gender[p] = Ma; > 63 rec_fill(p); > 64 if(!ok) > 65 return ok; > 66 } > 67 } > 68 return ok; > 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 string& Expected, const string& 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(_, Family().isFamily(parent1, parent2));} > 86 int main(){ > 87 > 88 CASE(0) > 89 int parent1_[] = {-1,-1,0}; > 90 vector <int> parent1(parent1_, parent1_+sizeof(parent1_)/sizeof(*paren > 91 int parent2_[] = {-1,-1,1}; > 92 vector <int> parent2(parent2_, parent2_+sizeof(parent2_)/sizeof(*paren > 93 string _ = "Possible"; > 94 END > 95 CASE(1) > 96 int parent1_[] = {-1,-1,-1,-1,-1}; > 97 vector <int> parent1(parent1_, parent1_+sizeof(parent1_)/sizeof(*paren > 98 int parent2_[] = {-1,-1,-1,-1,-1}; > 99 vector <int> parent2(parent2_, parent2_+sizeof(parent2_)/sizeof(*paren > 100 string _ = "Possible"; > 101 END > 102 CASE(2) > 103 int parent1_[] = {-1,-1,0,0,1}; > 104 vector <int> parent1(parent1_, parent1_+sizeof(parent1_)/sizeof(*paren > 105 int parent2_[] = {-1,-1,1,2,2}; > 106 vector <int> parent2(parent2_, parent2_+sizeof(parent2_)/sizeof(*paren > 107 string _ = "Impossible"; > 108 END > 109 CASE(3) > 110 int parent1_[] = {-1,-1,-1,-1,1,-1,0,5,6,-1,0,3,8,6} > 111 ; > 112 vector <int> parent1(parent1_, parent1_+sizeof(parent1_)/sizeof(*paren > 113 int parent2_[] = {-1,-1,-1,-1,3,-1,4,6,5,-1,5,4,6,1} > 114 ; > 115 vector <int> parent2(parent2_, parent2_+sizeof(parent2_)/sizeof(*paren > 116 string _ = "Possible"; > 117 END > 118 CASE(4) > 119 int parent1_[] = {-1,-1,-1,2,2,-1,5,6,4,6,2,1,8,0,2,4,6,9,-1,16,-1,11}; > 120 vector <int> parent1(parent1_, parent1_+sizeof(parent1_)/sizeof(*paren > 121 int parent2_[] = {-1,-1,-1,1,0,-1,1,4,2,0,4,8,2,3,0,5,14,14,-1,7,-1,13}; > 122 vector <int> parent2(parent2_, parent2_+sizeof(parent2_)/sizeof(*paren > 123 string _ = "Impossible"; > 124 END > 125 /* > 126 CASE(5) > 127 int parent1_[] = ; > 128 vector <int> parent1(parent1_, parent1_+sizeof(parent1_)/sizeof(*paren > 129 int parent2_[] = ; > 130 vector <int> parent2(parent2_, parent2_+sizeof(parent2_)/sizeof(*paren > 131 string _ = ; > 132 END > 133 CASE(6) > 134 int parent1_[] = ; > 135 vector <int> parent1(parent1_, parent1_+sizeof(parent1_)/sizeof(*paren > 136 int parent2_[] = ; > 137 vector <int> parent2(parent2_, parent2_+sizeof(parent2_)/sizeof(*paren > 138 string _ = ; > 139 END > 140 */ > 141 } > 142 // END CUT HERE
Added SRM/619-U/1B-U.cpp version [68f91e93f6818277]
> 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 MovingRooksDiv1 { public: > 23 vector <int> move(vector <int> Y1, vector <int> Y2) > 24 { > 25 const int N = Y1.size(); > 26 vector<int> ans; > 27 > 28 for(int i=0; i<N; ++i) > 29 { > 30 if(Y1[i] < Y2[i]) > 31 return vector<int>(1, -1); > 32 else if(Y1[i] > Y2[i]) > 33 { > 34 vector<int> idx; > 35 idx.push_back(i); > 36 for(int k=i+1;; ++k) > 37 { > 38 if(Y1[idx.back()] > Y1[k]) > 39 idx.push_back(k); > 40 if(Y1[k] == Y2[i]) > 41 break; > 42 } > 43 for(int k=idx.size()-2; k>=0; --k) { > 44 ans.push_back(idx[k]); > 45 ans.push_back(idx[k+1]); > 46 swap(Y1[idx[k]], Y1[idx[k+1]]); > 47 } > 48 } > 49 } > 50 if(ans.size() > 2500) > 51 ans.resize(2500); > 52 return ans; > 53 } > 54 }; > 55 > 56 // BEGIN CUT HERE > 57 #include <ctime> > 58 double start_time; string timer() > 59 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 60 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 61 { os << "{ "; > 62 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 63 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 64 void verify_case(const vector <int>& Expected, const vector <int>& Received) { > 65 bool ok = (Expected == Received); > 66 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 67 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 68 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 69 #define END verify_case(_, MovingRooksDiv1().move(Y1, Y2));} > 70 int main(){ > 71 > 72 CASE(0) > 73 int Y1_[] = {0}; > 74 vector <int> Y1(Y1_, Y1_+sizeof(Y1_)/sizeof(*Y1_)); > 75 int Y2_[] = {0}; > 76 vector <int> Y2(Y2_, Y2_+sizeof(Y2_)/sizeof(*Y2_)); > 77 vector <int> _; > 78 END > 79 CASE(1) > 80 int Y1_[] = {1,0}; > 81 vector <int> Y1(Y1_, Y1_+sizeof(Y1_)/sizeof(*Y1_)); > 82 int Y2_[] = {0,1}; > 83 vector <int> Y2(Y2_, Y2_+sizeof(Y2_)/sizeof(*Y2_)); > 84 int __[] = {0, 1 }; > 85 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 86 END > 87 CASE(2) > 88 int Y1_[] = {1,2,0}; > 89 vector <int> Y1(Y1_, Y1_+sizeof(Y1_)/sizeof(*Y1_)); > 90 int Y2_[] = {2,0,1}; > 91 vector <int> Y2(Y2_, Y2_+sizeof(Y2_)/sizeof(*Y2_)); > 92 int __[] = {-1 }; > 93 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 94 END > 95 CASE(3) > 96 int Y1_[] = {2,1,0,3,5,4}; > 97 vector <int> Y1(Y1_, Y1_+sizeof(Y1_)/sizeof(*Y1_)); > 98 int Y2_[] = {0,1,2,3,4,5}; > 99 vector <int> Y2(Y2_, Y2_+sizeof(Y2_)/sizeof(*Y2_)); > 100 int __[] = {0, 1, 0, 2, 1, 2, 4, 5 }; > 101 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 102 END > 103 CASE(4) > 104 int Y1_[] = {10,9,8,7,6,5,4,3,2,1,0}; > 105 vector <int> Y1(Y1_, Y1_+sizeof(Y1_)/sizeof(*Y1_)); > 106 int Y2_[] = {0,1,2,3,4,5,6,7,8,9,10}; > 107 vector <int> Y2(Y2_, Y2_+sizeof(Y2_)/sizeof(*Y2_)); > 108 int __[] = {0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8, 0, 9, 0, 10, > 109 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 110 END > 111 CASE(5) > 112 int Y1_[] = {2,1,0}; > 113 vector <int> Y1(Y1_, Y1_+sizeof(Y1_)/sizeof(*Y1_)); > 114 int Y2_[] = {0,2,1}; > 115 vector <int> Y2(Y2_, Y2_+sizeof(Y2_)/sizeof(*Y2_)); > 116 int __[] = {123456789}; > 117 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 118 END > 119 /* > 120 CASE(6) > 121 int Y1_[] = ; > 122 vector <int> Y1(Y1_, Y1_+sizeof(Y1_)/sizeof(*Y1_)); > 123 int Y2_[] = ; > 124 vector <int> Y2(Y2_, Y2_+sizeof(Y2_)/sizeof(*Y2_)); > 125 int __[] = ; > 126 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 127 END > 128 */ > 129 } > 130 // END CUT HERE
Added SRM/619-U/1C.cpp version [8609bba59add5d74]
> 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_.si > 44 > 45 class LongWordsDiv1 { public: > 46 int count(int n) > 47 { > 48 vector<mint> dp(n+1); > 49 dp[0] = 0; > 50 dp[1] = 1; > 51 for(int x=2; x<=n; ++x) > 52 { > 53 mint total = dp[x-1]; > 54 for(int k=1; k<=x-1; ++k) > 55 total += dp[k] * dp[x-1-k]; > 56 dp[x] = total; > 57 } > 58 return (dp[n] * FAC(n)).val; > 59 } > 60 }; > 61 > 62 // BEGIN CUT HERE > 63 #include <ctime> > 64 double start_time; string timer() > 65 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 66 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 67 { os << "{ "; > 68 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 69 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 70 void verify_case(const int& Expected, const int& Received) { > 71 bool ok = (Expected == Received); > 72 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 73 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 74 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 75 #define END verify_case(_, LongWordsDiv1().count(n));} > 76 int main(){ > 77 > 78 CASE(0) > 79 int n = 1; > 80 int _ = 1; > 81 END > 82 CASE(1) > 83 int n = 2; > 84 int _ = 2; > 85 END > 86 CASE(2) > 87 int n = 5; > 88 int _ = 1080; > 89 END > 90 CASE(3) > 91 int n = 100; > 92 int _ = 486425238; > 93 END > 94 /* > 95 CASE(4) > 96 int n = ; > 97 int _ = ; > 98 END > 99 CASE(5) > 100 int n = ; > 101 int _ = ; > 102 END > 103 */ > 104 } > 105 // END CUT HERE