Overview
| SHA1 Hash: | 9f60383a2c764956593f292c5541618cc02a0093 |
|---|---|
| Date: | 2012-06-16 15:43:23 |
| User: | kinaba |
| Comment: | renshuu |
| 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/538-U/1A.cpp version [0119219fe783de06]
> 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 EvenRoute { public: > 23 string isItPossible(vector <int> x, vector <int> y, int wantedParity) > 24 { > 25 bool can = false; > 26 for(int i=0; i<x.size(); ++i) > 27 if( ((x[i]+y[i])&1) == wantedParity ) > 28 can = true; > 29 return can ? "CAN" : "CANNOT"; > 30 } > 31 }; > 32 > 33 // BEGIN CUT HERE > 34 #include <ctime> > 35 double start_time; string timer() > 36 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 37 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 38 { os << "{ "; > 39 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 40 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 41 void verify_case(const string& Expected, const string& Received) { > 42 bool ok = (Expected == Received); > 43 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 44 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 45 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 46 #define END verify_case(_, EvenRoute().isItPossible(x, y, wantedParity));} > 47 int main(){ > 48 > 49 CASE(0) > 50 int x_[] = {-1,-1,1,1}; > 51 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 52 int y_[] = {-1,1,1,-1}; > 53 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 54 int wantedParity = 0; > 55 string _ = "CAN"; > 56 END > 57 CASE(1) > 58 int x_[] = {-5,-3,2}; > 59 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 60 int y_[] = {2,0,3}; > 61 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 62 int wantedParity = 1; > 63 string _ = "CAN"; > 64 END > 65 CASE(2) > 66 int x_[] = {1001, -4000}; > 67 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 68 int y_[] = {0,0}; > 69 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 70 int wantedParity = 1; > 71 string _ = "CAN"; > 72 END > 73 CASE(3) > 74 int x_[] = {11, 21, 0}; > 75 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 76 int y_[] = {-20, 42, 7}; > 77 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 78 int wantedParity = 0; > 79 string _ = "CANNOT"; > 80 END > 81 CASE(4) > 82 int x_[] = {0, 6}; > 83 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 84 int y_[] = {10, -20}; > 85 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 86 int wantedParity = 1; > 87 string _ = "CANNOT"; > 88 END > 89 CASE(5) > 90 int x_[] = {159833,-62665,323889,-235879,137089,-669850,137554,549764,19 > 91 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 92 int y_[] = {38668,957082,-75351,-877610,-247852,458917,-417575,219160,51 > 93 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 94 int wantedParity = 0; > 95 string _ = "???"; > 96 END > 97 CASE(5) > 98 int x_[] = {159833,-62665,323889,-235879,137089,-669850,137554,549764,19 > 99 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 100 int y_[] = {38668,957082,-75351,-877610,-247852,458917,-417575,219160,51 > 101 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 102 int wantedParity = 1; > 103 string _ = "???"; > 104 END > 105 CASE(6) > 106 int x_[] = {159833,-62665,323889,-235879,137089,-669850,137554,549764,19 > 107 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 108 int y_[] = {159833,-62665,323889,-235879,137089,-669850,137554,549764,19 > 109 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 110 int wantedParity = 0; > 111 string _ = "???"; > 112 END > 113 CASE(6) > 114 int x_[] = {159833,-62665,323889,-235879,137089,-669850,137554,549764,19 > 115 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 116 int y_[] = {159833,-62665,323889,-235879,137089,-669850,137554,549764,19 > 117 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 118 int wantedParity = 1; > 119 string _ = "???"; > 120 END > 121 > 122 } > 123 // END CUT HERE
Added SRM/542-U/1A.cpp version [bb17ad1de9271516]
> 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 PatrolRoute { public: > 23 int countRoutes(int X, int Y, int minT, int maxT) > 24 { > 25 --X, --Y; > 26 > 27 LL count = 0; > 28 for(int W=2; W<=X; ++W) > 29 for(int H=2; H<=Y; ++H) > 30 if( minT <= (W+H)*2 && (W+H)*2 <= maxT ) > 31 count = (count + threePoints(W,H) * (X-W > 32 return count; > 33 } > 34 > 35 LL threePoints(int W, int H) > 36 { > 37 LL a = (W-1)*(H-1); > 38 LL b = (W-1)*(H-1); > 39 return 4*a + 2*b; > 40 } > 41 }; > 42 > 43 // BEGIN CUT HERE > 44 #include <ctime> > 45 double start_time; string timer() > 46 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 47 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 48 { os << "{ "; > 49 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 50 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 51 void verify_case(const int& Expected, const int& Received) { > 52 bool ok = (Expected == Received); > 53 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 54 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 55 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 56 #define END verify_case(_, PatrolRoute().countRoutes(X, Y, minT, maxT));} > 57 int main(){ > 58 > 59 CASE(0) > 60 int X = 3; > 61 int Y = 3; > 62 int minT = 1; > 63 int maxT = 20000; > 64 int _ = 6; > 65 END > 66 CASE(1) > 67 int X = 3; > 68 int Y = 3; > 69 int minT = 4; > 70 int maxT = 7; > 71 int _ = 0; > 72 END > 73 CASE(2) > 74 int X = 4; > 75 int Y = 6; > 76 int minT = 9; > 77 int maxT = 12; > 78 int _ = 264; > 79 END > 80 CASE(3) > 81 int X = 7; > 82 int Y = 5; > 83 int minT = 13; > 84 int maxT = 18; > 85 int _ = 1212; > 86 END > 87 CASE(4) > 88 int X = 4000; > 89 int Y = 4000; > 90 int minT = 4000; > 91 int maxT = 14000; > 92 int _ = 859690013; > 93 END > 94 CASE(5) > 95 int X = 4000; > 96 int Y = 4000; > 97 int minT = 1; > 98 int maxT = 20000; > 99 int _ = -1; > 100 END > 101 CASE(6) > 102 int X = 3; > 103 int Y = 3; > 104 int minT = 1; > 105 int maxT = 1; > 106 int _ = 0; > 107 END > 108 > 109 } > 110 // END CUT HERE
Added SRM/545-U/1A.cpp version [44a4e17ed83b1873]
> 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 StrIIRec { public: > 23 string recovstr(int n, int minInv, string minStr) > 24 { > 25 for(int i=0; i<n; ++i) > 26 if(minStr.find(char('a'+i)) == string::npos) > 27 minStr += char('a'+i); > 28 > 29 for(int i=n-1; i>=0; --i) { > 30 string pre = minStr.substr(0,i); > 31 string post = minStr.substr(i); > 32 sort(post.rbegin(), post.rend()); > 33 if( inv(pre+post) >= minInv ) > 34 if(i==n-1) { > 35 return pre+post; > 36 } else { > 37 string mid = ""; > 38 for(int m=i; m<n; ++m) > 39 { > 40 for(int k=post.size()-1; k>=0; - > 41 if((m==i && post[k]>minS > 42 string mmid = mi > 43 string ppost = p > 44 if( inv(pre+mmid > 45 mid = mm > 46 post = p > 47 goto nex > 48 } > 49 } > 50 nextM:; > 51 } > 52 return pre + mid; > 53 } > 54 } > 55 return "???"; > 56 } > 57 > 58 int inv(const string& s) > 59 { > 60 int cnt = 0; > 61 for(int i=0; i<s.size(); ++i) > 62 for(int j=i+1; j<s.size(); ++j) > 63 if(s[i]>s[j]) > 64 ++cnt; > 65 return cnt; > 66 } > 67 }; > 68 > 69 // BEGIN CUT HERE > 70 #include <ctime> > 71 double start_time; string timer() > 72 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 73 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 74 { os << "{ "; > 75 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 76 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 77 void verify_case(const string& Expected, const string& Received) { > 78 bool ok = (Expected == Received); > 79 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 80 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 81 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 82 #define END verify_case(_, StrIIRec().recovstr(n, minInv, minStr));} > 83 int main(){ > 84 > 85 CASE(0) > 86 int n = 2; > 87 int minInv = 1; > 88 string minStr = "ab"; > 89 string _ = "ba"; > 90 END > 91 CASE(1) > 92 int n = 9; > 93 int minInv = 1; > 94 string minStr = "efcdgab"; > 95 string _ = "efcdgabhi"; > 96 END > 97 CASE(2) > 98 int n = 11; > 99 int minInv = 55; > 100 string minStr = "debgikjfc"; > 101 string _ = "kjihgfedcba"; > 102 END > 103 CASE(3) > 104 int n = 15; > 105 int minInv = 0; > 106 string minStr = "e"; > 107 string _ = "eabcdfghijklmno"; > 108 END > 109 CASE(4) > 110 int n = 9; > 111 int minInv = 20; > 112 string minStr = "fcdebiha"; > 113 string _ = "fcdehigba"; > 114 END > 115 CASE(5) > 116 int n = 20; > 117 int minInv = 100; > 118 string minStr = "abcdefghijklmnopqrst"; > 119 string _ = "?"; > 120 END > 121 /* > 122 CASE(6) > 123 int n = ; > 124 int minInv = ; > 125 string minStr = ; > 126 string _ = ; > 127 END > 128 */ > 129 } > 130 // END CUT HERE
Added SRM/545-U/1B.cpp version [0f56b30fe14df222]
> 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 int MODVAL = 1000000007; > 23 struct mint > 24 { > 25 int val; > 26 mint():val(0){} > 27 mint(int x):val(x%MODVAL) {} > 28 mint(size_t 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 POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } > 35 mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); } > 36 mint operator+(mint x, mint y) { return x+=y; } > 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 vector<mint> FAC_(1,1); > 41 mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() > 42 //mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); } > 43 > 44 vector< vector<mint> > CP_; > 45 mint C(LL n, LL k) { > 46 while( CP_.size() <= n ) { > 47 int nn = CP_.size(); > 48 CP_.push_back(vector<mint>(nn+1,1)); > 49 for(int kk=1; kk<nn; ++kk) > 50 CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk]; > 51 } > 52 return k<0 || n<k ? 0 : CP_[n][k]; > 53 } > 54 > 55 int gcd(int a, int b) { > 56 while(a) > 57 swap(a, b%=a); > 58 return b; > 59 } > 60 > 61 class Spacetsk { public: > 62 int countsets(int L, int H, int K) > 63 { > 64 if( K==1 ) > 65 return (L+1)*(H+1); > 66 > 67 mint sum = 0; > 68 for(int x=0; x<=L; ++x) > 69 for(int y=1; y<=H; ++y) > 70 { > 71 mint dup = (x==0 ? L+1 : 2*(L+1-x)); > 72 mint mid = C(gcd(x, y), K-1); > 73 sum = sum + dup*mid; > 74 } > 75 return sum.val; > 76 } > 77 }; > 78 > 79 // BEGIN CUT HERE > 80 #include <ctime> > 81 double start_time; string timer() > 82 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 83 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 84 { os << "{ "; > 85 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 86 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 87 void verify_case(const int& Expected, const int& Received) { > 88 bool ok = (Expected == Received); > 89 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 90 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 91 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 92 #define END verify_case(_, Spacetsk().countsets(L, H, K));} > 93 int main(){ > 94 > 95 CASE(0) > 96 int L = 1; > 97 int H = 1; > 98 int K = 2; > 99 int _ = 4; > 100 END > 101 CASE(1) > 102 int L = 1; > 103 int H = 1; > 104 int K = 1; > 105 int _ = 4; > 106 END > 107 CASE(2) > 108 int L = 2; > 109 int H = 2; > 110 int K = 1; > 111 int _ = 9; > 112 END > 113 CASE(3) > 114 int L = 2; > 115 int H = 2; > 116 int K = 2; > 117 int _ = 23; > 118 END > 119 CASE(4) > 120 int L = 5; > 121 int H = 5; > 122 int K = 3; > 123 int _ = 202; > 124 END > 125 CASE(5) > 126 int L = 561; > 127 int H = 394; > 128 int K = 20; > 129 int _ = 786097180; > 130 END > 131 CASE(6) > 132 int L = 1; > 133 int H = 1; > 134 int K = 1; > 135 int _ = 4; > 136 END > 137 CASE(7) > 138 int L = 2000; > 139 int H = 2000; > 140 int K = 500; > 141 int _ = -1; > 142 END > 143 CASE(7) > 144 int L = 2000; > 145 int H = 2000; > 146 int K = 2; > 147 int _ = -1; > 148 END > 149 } > 150 // END CUT HERE