Overview
| SHA1 Hash: | f0a8c39350933c080ef9a856318cf98dd75ce33b |
|---|---|
| Date: | 2013-09-16 05:25:18 |
| User: | kinaba |
| Comment: | 590 |
| 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/590-U/1A.cpp version [a209bed380584b53]
> 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 FoxAndChess { public: > 23 string ableToMove(string begin, string target) > 24 { > 25 return solve(cb(begin), cb(target)) ? "Possible" : "Impossible"; > 26 } > 27 > 28 vector<pair<char,int>> cb(string s) > 29 { > 30 vector<pair<char,int>> v; > 31 for(int i=0; i<s.size(); ++i) > 32 if(s[i]!='.') > 33 v.emplace_back(s[i], i); > 34 return v; > 35 } > 36 > 37 bool solve(const vector<pair<char,int>>& b, const vector<pair<char,int>> > 38 { > 39 if(b.size() != e.size()) > 40 return false; > 41 for(int i=0; i<b.size(); ++i) { > 42 if(b[i].first != e[i].first) > 43 return false; > 44 if(b[i].first == 'L' && b[i].second<e[i].second) > 45 return false; > 46 if(b[i].first == 'R' && b[i].second>e[i].second) > 47 return false; > 48 } > 49 return true; > 50 } > 51 }; > 52 > 53 // BEGIN CUT HERE > 54 #include <ctime> > 55 double start_time; string timer() > 56 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 57 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 58 { os << "{ "; > 59 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 60 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 61 void verify_case(const string& Expected, const string& Received) { > 62 bool ok = (Expected == Received); > 63 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 64 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 65 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 66 #define END verify_case(_, FoxAndChess().ableToMove(begin, target));} > 67 int main(){ > 68 > 69 CASE(0) > 70 string begin = "R..."; > 71 string target = "..R."; > 72 string _ = "Possible"; > 73 END > 74 CASE(1) > 75 string begin = "..R."; > 76 string target = "R..."; > 77 string _ = "Impossible"; > 78 END > 79 CASE(2) > 80 string begin = ".L.R.R."; > 81 string target = "L...R.R"; > 82 string _ = "Possible"; > 83 END > 84 CASE(3) > 85 string begin = ".L.R."; > 86 string target = ".R.L."; > 87 string _ = "Impossible"; > 88 END > 89 CASE(4) > 90 string begin = "LRLLRLRLLRLLRLRLRL"; > 91 string target = "LRLLRLRLLRLLRLRLRL"; > 92 string _ = "Possible"; > 93 END > 94 CASE(5) > 95 string begin = "L"; > 96 string target = "."; > 97 string _ = "Impossible"; > 98 END > 99 /* > 100 CASE(6) > 101 string begin = ; > 102 string target = ; > 103 string _ = ; > 104 END > 105 CASE(7) > 106 string begin = ; > 107 string target = ; > 108 string _ = ; > 109 END > 110 */ > 111 } > 112 // END CUT HERE
Added SRM/590-U/1B.cpp version [8a48c9e039e2e851]
> 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 XorCards { public: > 23 long long numberOfWays(vector<long long> number, long long limit) > 24 { > 25 LL total = 0; > 26 LL req = 0; > 27 for(int k=62; k>=0; --k) > 28 if(limit & (1LL<<k)) > 29 { > 30 total += sub(number, k, req); > 31 req |= 1LL << k; > 32 } > 33 total += sub(number, 0, req); > 34 return total; > 35 } > 36 > 37 LL sub(vector<LL> num, int k, LL req) > 38 { > 39 for(auto& v : num) v>>=k; > 40 return exact_equal(num, req>>k); > 41 } > 42 > 43 LL exact_equal(const vector<LL>& xs, LL target) > 44 { > 45 int H = 50; > 46 int W = xs.size(); > 47 vector<vector<int>> M(H, vector<int>(W)); > 48 for(int y=0; y<H; ++y) > 49 for(int x=0; x<W; ++x) > 50 M[y][x] = (xs[x]>>y)&1; > 51 vector<int> V(H); > 52 for(int y=0; y<H; ++y) > 53 V[y] = (target>>y)&1; > 54 return num_solution(H, W, M, V); > 55 } > 56 > 57 LL num_solution(int H, int W, vector<vector<int>>& M, vector<int>& V) > 58 { > 59 int skipx = 0; > 60 int y = 0; > 61 for(int x=0; y<H && x<W; ++x) > 62 { > 63 if(M[y][x] == 0) { > 64 bool found = false; > 65 for(int yy=y+1; yy<H; ++yy) > 66 if(M[yy][x] == 1) { > 67 swap(M[y], M[yy]); > 68 swap(V[y], V[yy]); > 69 found = true; > 70 break; > 71 } > 72 if(!found) { > 73 ++skipx; > 74 continue; > 75 } > 76 } > 77 > 78 for(int yy=y+1; yy<H; ++yy) > 79 if(M[yy][x] == 1) { > 80 for(int xx=x; xx<W; ++xx) > 81 M[yy][xx] ^= M[y][xx]; > 82 V[yy] ^= V[y]; > 83 } > 84 ++y; > 85 } > 86 for(int yy=y; yy<H; ++yy) > 87 if(V[yy] == 1) > 88 return 0; > 89 return 1LL << skipx; > 90 } > 91 }; > 92 > 93 // BEGIN CUT HERE > 94 #include <ctime> > 95 double start_time; string timer() > 96 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 97 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 98 { os << "{ "; > 99 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 100 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 101 void verify_case(const long long& Expected, const long long& Received) { > 102 bool ok = (Expected == Received); > 103 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 104 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 105 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 106 #define END verify_case(_, XorCards().numberOfWays(number, limit));} > 107 int main(){ > 108 > 109 CASE(0) > 110 long long number_[] = {1,2}; > 111 vector<long long> number(number_, number_+sizeof(number_)/sizeof(*numb > 112 long long limit = 2LL; > 113 long long _ = 3LL; > 114 END > 115 CASE(1) > 116 long long number_[] = {5,5}; > 117 vector<long long> number(number_, number_+sizeof(number_)/sizeof(*numb > 118 long long limit = 3LL; > 119 long long _ = 2LL; > 120 END > 121 CASE(2) > 122 long long number_[] = {1,2,3,4,5,6,7}; > 123 vector<long long> number(number_, number_+sizeof(number_)/sizeof(*numb > 124 long long limit = 5LL; > 125 long long _ = 96LL; > 126 END > 127 CASE(3) > 128 long long number_[] = {123, 456, 789, 147, 258, 369, 159, 357}; > 129 vector<long long> number(number_, number_+sizeof(number_)/sizeof(*numb > 130 long long limit = 500LL; > 131 long long _ = 125LL; > 132 END > 133 CASE(4) > 134 long long number_[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 > 135 vector<long long> number(number_, number_+sizeof(number_)/sizeof(*numb > 136 long long limit = 1000000000000000LL; > 137 long long _ = 4294967296LL; > 138 END > 139 CASE(5) > 140 long long number_[] = {1000000000000000, 999999999999999}; > 141 vector<long long> number(number_, number_+sizeof(number_)/sizeof(*numb > 142 long long limit = 65535LL; > 143 long long _ = 2LL; > 144 END > 145 CASE(6) > 146 long long number_[] = {892821358,637693537,31021825,911417798,989152798, > 147 vector<long long> number(number_, number_+sizeof(number_)/sizeof(*numb > 148 long long limit = 225387446LL; > 149 long long _ = -1LL; > 150 END > 151 CASE(7) > 152 long long number_[] = {0}; > 153 vector<long long> number(number_, number_+sizeof(number_)/sizeof(*numb > 154 long long limit = 1LL; > 155 long long _ = 2LL; > 156 END > 157 > 158 } > 159 // END CUT HERE