Overview
| SHA1 Hash: | f33265e95ca5856ff582b65507f2d5d6b7c054a6 |
|---|---|
| Date: | 2014-09-05 10:21:57 |
| User: | kinaba |
| Comment: | 631 |
| 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/631-U/1A.cpp version [db13cb4122e4e0d1]
> 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 TaroJiroGrid { public: > 23 int getNumber(vector <string> grid) > 24 { > 25 const int H = grid.size(); > 26 const int W = grid[0].size(); > 27 const string Change[2] = {string(W, 'B'), string(W, 'W')}; > 28 > 29 // 0 > 30 if(ok(grid)) > 31 return 0; > 32 // 1 > 33 for(int y1=0; y1<H; ++y1) for(int c1=0; c1<2; ++c1) { > 34 auto t1 = grid[y1]; > 35 grid[y1] = Change[c1]; > 36 if(ok(grid)) return 1; > 37 grid[y1] = t1; > 38 } > 39 return 2; > 40 } > 41 > 42 bool ok(const vector<string>& g) > 43 { > 44 const int H = g.size(); > 45 const int W = g[0].size(); > 46 for(int x=0; x<W; ++x) { > 47 int nb=0, nw=0; > 48 for(int y=0; y<H; ++y) > 49 { > 50 if(g[y][x]=='B') nb++, nw=0; > 51 else nb=0, nw++; > 52 if(nw>H/2 || nb>H/2) > 53 return false; > 54 } > 55 } > 56 return true; > 57 } > 58 }; > 59 > 60 // BEGIN CUT HERE > 61 #include <ctime> > 62 double start_time; string timer() > 63 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 64 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 65 { os << "{ "; > 66 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 67 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 68 void verify_case(const int& Expected, const int& Received) { > 69 bool ok = (Expected == Received); > 70 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 71 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 72 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 73 #define END verify_case(_, TaroJiroGrid().getNumber(grid));} > 74 int main(){ > 75 > 76 CASE(0) > 77 string grid_[] = {"WB", > 78 "BB"}; > 79 vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); > 80 int _ = 1; > 81 END > 82 CASE(1) > 83 string grid_[] = {"WB", > 84 "WW"}; > 85 vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); > 86 int _ = 1; > 87 END > 88 CASE(2) > 89 string grid_[] = {"WB", > 90 "WB"}; > 91 vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); > 92 int _ = 2; > 93 END > 94 CASE(3) > 95 string grid_[] = {"WBBW", > 96 "WBWB", > 97 "WWBB", > 98 "BWWW"}; > 99 vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); > 100 int _ = 2; > 101 END > 102 CASE(4) > 103 string grid_[] = {"WBBWBB", > 104 "BBWBBW", > 105 "WWBWBW", > 106 "BWWBBB", > 107 "WBWBBW", > 108 "WWWBWB"}; > 109 vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); > 110 int _ = 1; > 111 END > 112 /* > 113 CASE(5) > 114 string grid_[] = ; > 115 vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); > 116 int _ = ; > 117 END > 118 CASE(6) > 119 string grid_[] = ; > 120 vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); > 121 int _ = ; > 122 END > 123 */ > 124 } > 125 // END CUT HERE
Added SRM/631-U/1B-U.cpp version [0ca2f3e8b8b48b53]
> 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 CatsOnTheLineDiv1 { public: > 23 int getNumber(vector <int> position, vector <int> count, int time) > 24 { > 25 const int N = position.size(); > 26 vector<pair<int,int>> pc; > 27 for(int i=0; i<N; ++i) pc.emplace_back(position[i], count[i]); > 28 sort(pc.begin(), pc.end()); > 29 > 30 map<LL,int> dp; > 31 dp[(-400000000LL)<<32] = 0; > 32 for(auto& pci: pc) { > 33 const int p = pci.first; > 34 const int c = pci.second; > 35 map<LL,int> dp2; > 36 for(auto& tk: dp) { > 37 const LL t = tk.first; > 38 const int k = tk.second; > 39 const int occ_x = int(t>>32); > 40 const int has_wan = t&0x80000000; > 41 const int wan_x = int(t&0x3fffffff); > 42 > 43 int myleft = max(p-time, occ_x+1); > 44 int myright = myleft + c - 1; > 45 if(myright <= p+time) { > 46 LL key = (LL(myright)<<32) | has_wan | w > 47 int v = k; > 48 cerr << "#" << myright << " " << (has_wa > 49 if(dp2.count(key)) dp2[key] = min(dp2[ke > 50 } > 51 if(has_wan && p-time <= wan_x) { > 52 LL key = LL(occ_x)<<32 | 0x80000000 | wa > 53 int v = k; > 54 cerr << "$" << occ_x << " " << 1 << " " > 55 if(dp2.count(key)) dp2[key] = min(dp2[ke > 56 } > 57 { > 58 LL key = LL(occ_x)<<32 | 0x80000000 | (p > 59 int v = k + (has_wan?1:0); > 60 cerr << "!" << occ_x << " " << 1 << " " > 61 if(dp2.count(key)) dp2[key] = min(dp2[ke > 62 } > 63 } > 64 dp = std::move(dp2); > 65 } > 66 > 67 int best = N; > 68 for(auto& tk: dp) { > 69 const LL t = tk.first; > 70 const int k = tk.second; > 71 const int occ_x = int(t>>32); > 72 const int has_wan = t&0x80000000; > 73 const int wan_x = int(t&0x3fffffff); > 74 best = min(best, k + (has_wan?1:0)); > 75 } > 76 return best; > 77 } > 78 }; > 79 > 80 // BEGIN CUT HERE > 81 #include <ctime> > 82 double start_time; string timer() > 83 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 84 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 85 { os << "{ "; > 86 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 87 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 88 void verify_case(const int& Expected, const int& Received) { > 89 bool ok = (Expected == Received); > 90 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 91 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 92 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 93 #define END verify_case(_, CatsOnTheLineDiv1().getNumber(position, count, t > 94 int main(){ > 95 > 96 CASE(0) > 97 int position_[] = {0}; > 98 vector <int> position(position_, position_+sizeof(position_)/sizeof(*p > 99 int count_[] = {7}; > 100 vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_)); > 101 int time = 3; > 102 int _ = 0; > 103 END > 104 CASE(1) > 105 int position_[] = {0}; > 106 vector <int> position(position_, position_+sizeof(position_)/sizeof(*p > 107 int count_[] = {6}; > 108 vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_)); > 109 int time = 2; > 110 int _ = 1; > 111 END > 112 CASE(2) > 113 int position_[] = {4, 7, 47}; > 114 vector <int> position(position_, position_+sizeof(position_)/sizeof(*p > 115 int count_[] = {4, 7, 4}; > 116 vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_)); > 117 int time = 1; > 118 int _ = 3; > 119 END > 120 CASE(3) > 121 int position_[] = {3, 0, 7, 10}; > 122 vector <int> position(position_, position_+sizeof(position_)/sizeof(*p > 123 int count_[] = {3, 7, 4, 5}; > 124 vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_)); > 125 int time = 2; > 126 int _ = 2; > 127 END > 128 CASE(4) > 129 int position_[] = {-5, 0, 7}; > 130 vector <int> position(position_, position_+sizeof(position_)/sizeof(*p > 131 int count_[] = {47, 85, 10}; > 132 vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_)); > 133 int time = 6; > 134 int _ = 1; > 135 END > 136 CASE(5) > 137 int position_[] = {-8, 12, -15, -20, 17, -5, 7, 10}; > 138 vector <int> position(position_, position_+sizeof(position_)/sizeof(*p > 139 int count_[] = {20, 10, 7, 9, 2, 8, 11, 10}; > 140 vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_)); > 141 int time = 2; > 142 int _ = 5; > 143 END > 144 /* > 145 CASE(6) > 146 int position_[] = ; > 147 vector <int> position(position_, position_+sizeof(position_)/sizeof(*p > 148 int count_[] = ; > 149 vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_)); > 150 int time = ; > 151 int _ = ; > 152 END > 153 CASE(7) > 154 int position_[] = ; > 155 vector <int> position(position_, position_+sizeof(position_)/sizeof(*p > 156 int count_[] = ; > 157 vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_)); > 158 int time = ; > 159 int _ = ; > 160 END > 161 */ > 162 } > 163 // END CUT HERE