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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 44 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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,191807,993220,-801864,-425902,326896,312318,-778686,33030,763633,-866343,36938,-627234,-19941,-909928,-920678,-763769,657773,431660,600784,54912,563394,970744,872933,-413697,319375,249696,368559,-449659,942650,997004,-420096,-473219,-757172,70934,-771310,498140,-870998,176429,985061,-674033,255167,-89503}; 91 + vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 92 + int y_[] = {38668,957082,-75351,-877610,-247852,458917,-417575,219160,515259,-254435,-441099,631589,-637191,-902042,-662042,-279031,-233412,-443322,207905,-566785,-248122,829715,362587,831403,-238955,792643,77852,665108,83526,-623925,-199287,492427,311357,-437880,39341,988852,-261007,-621546,-659372,-661305,196329,769159,-771255,-888939,483180,-151127,-533736,281297,411246,-339825}; 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,191807,993220,-801864,-425902,326896,312318,-778686,33030,763633,-866343,36938,-627234,-19941,-909928,-920678,-763769,657773,431660,600784,54912,563394,970744,872933,-413697,319375,249696,368559,-449659,942650,997004,-420096,-473219,-757172,70934,-771310,498140,-870998,176429,985061,-674033,255167,-89503}; 99 + vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 100 + int y_[] = {38668,957082,-75351,-877610,-247852,458917,-417575,219160,515259,-254435,-441099,631589,-637191,-902042,-662042,-279031,-233412,-443322,207905,-566785,-248122,829715,362587,831403,-238955,792643,77852,665108,83526,-623925,-199287,492427,311357,-437880,39341,988852,-261007,-621546,-659372,-661305,196329,769159,-771255,-888939,483180,-151127,-533736,281297,411246,-339825}; 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,191807,993220,-801864,-425902,326896,312318,-778686,33030,763633,-866343,36938,-627234,-19941,-909928,-920678,-763769,657773,431660,600784,54912,563394,970744,872933,-413697,319375,249696,368559,-449659,942650,997004,-420096,-473219,-757172,70934,-771310,498140,-870998,176429,985061,-674033,255167,-89503}; 107 + vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 108 + int y_[] = {159833,-62665,323889,-235879,137089,-669850,137554,549764,191807,993220,-801864,-425902,326896,312318,-778686,33030,763633,-866343,36938,-627234,-19941,-909928,-920678,-763769,657773,431660,600784,54912,563394,970744,872933,-413697,319375,249696,368559,-449659,942650,997004,-420096,-473219,-757172,70934,-771310,498140,-870998,176429,985061,-674033,255167,-89503}; 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,191807,993220,-801864,-425902,326896,312318,-778686,33030,763633,-866343,36938,-627234,-19941,-909928,-920678,-763769,657773,431660,600784,54912,563394,970744,872933,-413697,319375,249696,368559,-449659,942650,997004,-420096,-473219,-757172,70934,-771310,498140,-870998,176429,985061,-674033,255167,-89503}; 115 + vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 116 + int y_[] = {159833,-62665,323889,-235879,137089,-669850,137554,549764,191807,993220,-801864,-425902,326896,312318,-778686,33030,763633,-866343,36938,-627234,-19941,-909928,-920678,-763769,657773,431660,600784,54912,563394,970744,872933,-413697,319375,249696,368559,-449659,942650,997004,-420096,-473219,-757172,70934,-771310,498140,-870998,176429,985061,-674033,255167,-89503}; 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+1)*(Y-H+1)) % 1000000007; 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 54 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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; --k) 41 + if((m==i && post[k]>minStr[i]) || (m!=i)) { 42 + string mmid = mid + post[k]; 43 + string ppost = post.substr(0,k) + post.substr(k+1); 44 + if( inv(pre+mmid+ppost) >= minInv ) { 45 + mid = mmid; 46 + post = ppost; 47 + goto nextM; 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 80 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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() ); return FAC_[n]; } 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 90 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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