Overview
| SHA1 Hash: | 7764536bd328f230ce5aeaab131495038c08ea7f |
|---|---|
| Date: | 2013-11-29 01:30:45 |
| User: | kinaba |
| Comment: | 597 |
| 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/597-U/1A.cpp version [1d6eb8d5bd0ebac2]
> 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 LittleElephantAndString { public: > 23 int getNumber(string A, string B) > 24 { > 25 string AA = A, BB = B; > 26 sort(AA.begin(), AA.end()); > 27 sort(BB.begin(), BB.end()); > 28 if(AA != BB) > 29 return -1; > 30 for(int n=0; n<B.size(); ++n) > 31 if(sup_sub(A, B.substr(n))) > 32 return n; > 33 assert(false); > 34 } > 35 > 36 bool sup_sub(const string& A, const string& B) > 37 { > 38 for(int a=0, b=0; b<B.size(); ++a,++b) > 39 { > 40 while(a<A.size() && A[a]!=B[b]) > 41 ++a; > 42 if(a == A.size()) > 43 return false; > 44 } > 45 return true; > 46 } > 47 }; > 48 > 49 // BEGIN CUT HERE > 50 #include <ctime> > 51 double start_time; string timer() > 52 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 53 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 54 { os << "{ "; > 55 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 56 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 57 void verify_case(const int& Expected, const int& Received) { > 58 bool ok = (Expected == Received); > 59 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 60 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 61 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 62 #define END verify_case(_, LittleElephantAndString().getNumber(A, B));} > 63 int main(){ > 64 > 65 CASE(0) > 66 string A = "ABC"; > 67 string B = "CBA"; > 68 int _ = 2; > 69 END > 70 CASE(1) > 71 string A = "A"; > 72 string B = "B"; > 73 int _ = -1; > 74 END > 75 CASE(2) > 76 string A = "AAABBB"; > 77 string B = "BBBAAA"; > 78 int _ = 3; > 79 END > 80 CASE(3) > 81 string A = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; > 82 string B = "ZYXWVUTSRQPONMLKJIHGFEDCBA"; > 83 int _ = 25; > 84 END > 85 CASE(4) > 86 string A = "A"; > 87 string B = "A"; > 88 int _ = 0; > 89 END > 90 CASE(5) > 91 string A = "DCABA"; > 92 string B = "DACBA"; > 93 int _ = 2; > 94 END > 95 /* > 96 CASE(6) > 97 string A = ; > 98 string B = ; > 99 int _ = ; > 100 END > 101 CASE(7) > 102 string A = ; > 103 string B = ; > 104 int _ = ; > 105 END > 106 */ > 107 } > 108 // END CUT HERE
Added SRM/597-U/1B.cpp version [ddf4c7315f5e5a02]
> 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 LL gcd(LL a, LL b) > 23 { > 24 while(a) > 25 swap(a, b%=a); > 26 return b; > 27 } > 28 > 29 class ConvexPolygonGame { public: > 30 string winner(vector <int> X, vector <int> Y) > 31 { > 32 return has_int_triangle(X, Y) ? "Masha" : "Petya"; > 33 } > 34 > 35 bool has_int_triangle(const vector<int>& X, const vector<int>& Y) > 36 { > 37 const int xm = *min_element(X.begin(), X.end()); > 38 const int xM = *max_element(X.begin(), X.end()); > 39 > 40 vector< pair<int,int> > p; > 41 > 42 int nc = 0, two = 0, dis = 0; > 43 for(int x=xm; x<=xM; ++x) > 44 { > 45 int ym, yM; > 46 tie(ym, yM) = y_range(x, X, Y); > 47 if(ym <= yM) { > 48 dis ++; > 49 nc += (yM - ym + 1); > 50 if(yM-ym+1 >= 2) > 51 two ++; > 52 else > 53 p.emplace_back(x, ym); > 54 } > 55 // cerr << nc << "," << two << " : " << x << " " << ym << " > 56 if(nc>=3 && two>=1 && dis>=2) > 57 return true; > 58 } > 59 if(nc>=3 && two==0 && dis>=2) > 60 { > 61 double am, aM; > 62 for(int i=1; i<p.size(); ++i) > 63 { > 64 double a = double(p[i].second - p[0].second) / ( > 65 if(i==1)am=aM=a; > 66 else am=min(am, a), aM=max(aM,a); > 67 } > 68 return (aM-am) > 1e-9; > 69 } > 70 return false; > 71 } > 72 > 73 tuple<int,int> y_range(int x, const vector<int>& X, const vector<int>& Y > 74 { > 75 vector< pair<LL,LL> > cross; > 76 vector< pair<LL,LL> > exact; > 77 > 78 const int N = X.size(); > 79 for(int i=0; i<N; ++i) > 80 { > 81 int x1=X[i], x2=X[(i+1)%N]; > 82 int y1=Y[i], y2=Y[(i+1)%N]; > 83 if(x1 > x2) > 84 swap(x1, x2), swap(y1, y2); > 85 > 86 if(x1 == x2) > 87 { > 88 if(x == x1) { > 89 cross.emplace_back(y1,1); > 90 cross.emplace_back(y2,1); > 91 exact.emplace_back(y1,1); > 92 exact.emplace_back(y2,1); > 93 } > 94 } > 95 else > 96 { > 97 if(x<x1 || x2<x) > 98 continue; > 99 LL q = LL(y2-y1)*(x-x1) + LL(y1)*(x2-x1); > 100 LL d = LL(x2-x1); > 101 LL g = gcd(abs(q), d); > 102 cross.emplace_back(q/g, d/g); > 103 if(x==x1 || x==x2) > 104 exact.emplace_back(q/g, d/g); > 105 } > 106 } > 107 > 108 sort(cross.begin(), cross.end()); > 109 cross.erase(unique(cross.begin(), cross.end()), cross.end()); > 110 if(cross.size() == 2) { > 111 LL q1 = cross[0].first; > 112 LL d1 = cross[0].second; > 113 LL q2 = cross[1].first; > 114 LL d2 = cross[1].second; > 115 if(q1*d2 > q2*d1) > 116 swap(q1,q2), swap(d1,d2); > 117 int ym = ceil_div(q1, d1); > 118 int yM = floor_div(q2, d2); > 119 bool ym_exact = false, yM_exact = false; > 120 for(int i=0; i<exact.size(); ++i) { > 121 if(ym*exact[i].second == exact[i].first) > 122 ym_exact = true; > 123 if(yM*exact[i].second == exact[i].first) > 124 yM_exact = true; > 125 } > 126 return make_tuple(ym_exact ? ym+1 : ym, yM_exact ? yM-1 > 127 } > 128 return make_tuple(-9998, -9999); > 129 } > 130 > 131 static int floor_div(LL a, LL b) > 132 { > 133 if(a>=0) return int(a/b); > 134 return int(-((-a+b-1)/b)); > 135 } > 136 > 137 static int ceil_div(LL a, LL b) > 138 { > 139 if(a>=0) return int((a+b-1)/b); > 140 return int(-((-a)/b)); > 141 } > 142 }; > 143 > 144 // BEGIN CUT HERE > 145 #include <ctime> > 146 double start_time; string timer() > 147 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 148 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 149 { os << "{ "; > 150 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 151 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 152 void verify_case(const string& Expected, const string& Received) { > 153 bool ok = (Expected == Received); > 154 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 155 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 156 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 157 #define END verify_case(_, ConvexPolygonGame().winner(X, Y));} > 158 int main(){ > 159 > 160 CASE(0) > 161 int X_[] = {0, 1, 0}; > 162 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 163 int Y_[] = {0, 0, 1}; > 164 vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_)); > 165 string _ = "Petya"; > 166 END > 167 CASE(1) > 168 int X_[] = {0, 4, 2}; > 169 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 170 int Y_[] = {0, 0, 2}; > 171 vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_)); > 172 string _ = "Masha"; > 173 END > 174 CASE(2) > 175 int X_[] = {0, 100, 100, 0}; > 176 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 177 int Y_[] = {0, 0, 100, 100}; > 178 vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_)); > 179 string _ = "Masha"; > 180 END > 181 CASE(3) > 182 int X_[] = {0, 50, 100, 50}; > 183 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 184 int Y_[] = {0, -1, 0, 1}; > 185 vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_)); > 186 string _ = "Petya"; > 187 END > 188 CASE(4) > 189 int X_[] = {-100000, 100000, 100000, -100000}; > 190 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 191 int Y_[] = {-1, -1, 1, 1}; > 192 vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_)); > 193 string _ = "Masha"; > 194 END > 195 CASE(5) > 196 // 1 1 1 (yoko) > 197 int X_[] = {0, 3, 5, 3}; > 198 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 199 int Y_[] = {0, 0, 1, 1}; > 200 vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_)); > 201 string _ = "Masha"; > 202 END > 203 CASE(5) > 204 // 1 1 1 (tate) > 205 int X_[] = {0, 1, 1, 0}; > 206 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 207 int Y_[] = {0, 3, 5, 3}; > 208 vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_)); > 209 string _ = "Masha"; > 210 END > 211 CASE(6) > 212 // 3 (tate) // yoko ha sample > 213 int X_[] = {-1, 0, 1, 0}; > 214 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 215 int Y_[] = {0, -2, 0, 2}; > 216 vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_)); > 217 string _ = "Petya"; > 218 END > 219 } > 220 // END CUT HERE