Overview
| SHA1 Hash: | 2da323b3ad8be7c0ae18873b5d57c03aa8fc0fa2 |
|---|---|
| Date: | 2016-01-13 01:48:25 |
| User: | kinaba |
| Comment: | 676 |
| 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/676-U/1A.cpp version [4948478ca41a65d0]
> 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 WaterTank { public: > 23 double minOutputRate(vector <int> t, vector <int> x, int C) > 24 { > 25 double L=0, R=1000000; // (L,R] > 26 for(int _=0; _<10000; ++_) { > 27 double mid = (L+R)/2; > 28 (can(t, x, C, mid) ? R : L) = mid; > 29 } > 30 return R; > 31 } > 32 > 33 bool can(const vector<int>& t, const vector<int>& x, int C, double R) > 34 { > 35 double v = 0; > 36 for(int i=0; i<t.size(); ++i) { > 37 v = max(0.0, v+(x[i]-R)*t[i]); > 38 if(v > C) > 39 return false; > 40 } > 41 return true; > 42 } > 43 }; > 44 > 45 // BEGIN CUT HERE > 46 #include <ctime> > 47 double start_time; string timer() > 48 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 49 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 50 { os << "{ "; > 51 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 52 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 53 void verify_case(const double& Expected, const double& Received) { > 54 bool ok = (abs(Expected - Received) < 1e-9); > 55 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 56 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 57 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 58 #define END verify_case(_, WaterTank().minOutputRate(t, x, C));} > 59 int main(){ > 60 > 61 CASE(0) > 62 int t_[] = {3,3}; > 63 vector <int> t(t_, t_+sizeof(t_)/sizeof(*t_)); > 64 int x_[] = {1,2}; > 65 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 66 int C = 3; > 67 double _ = 0.9999999999999999; > 68 END > 69 CASE(1) > 70 int t_[] = {1,2,3,4,5}; > 71 vector <int> t(t_, t_+sizeof(t_)/sizeof(*t_)); > 72 int x_[] = {5,4,3,2,1}; > 73 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 74 int C = 10; > 75 double _ = 1.9999999999999996; > 76 END > 77 CASE(2) > 78 int t_[] = {5949,3198,376,3592,4019,3481,5609,3840,6092,4059}; > 79 vector <int> t(t_, t_+sizeof(t_)/sizeof(*t_)); > 80 int x_[] = {29,38,96,84,10,2,39,27,76,94}; > 81 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 82 int C = 1000000000; > 83 double _ = 0.0; > 84 END > 85 CASE(3) > 86 int t_[] = {9,3,4,8,1,2,5,7,6}; > 87 vector <int> t(t_, t_+sizeof(t_)/sizeof(*t_)); > 88 int x_[] = {123,456,789,1011,1213,1415,1617,1819,2021}; > 89 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 90 int C = 11; > 91 double _ = 2019.1666666666665; > 92 END > 93 CASE(4) > 94 int t_[] = {100}; > 95 vector <int> t(t_, t_+sizeof(t_)/sizeof(*t_)); > 96 int x_[] = {1000}; > 97 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 98 int C = 12345; > 99 double _ = 876.55; > 100 END > 101 /* > 102 CASE(5) > 103 int t_[] = ; > 104 vector <int> t(t_, t_+sizeof(t_)/sizeof(*t_)); > 105 int x_[] = ; > 106 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 107 int C = ; > 108 double _ = ; > 109 END > 110 CASE(6) > 111 int t_[] = ; > 112 vector <int> t(t_, t_+sizeof(t_)/sizeof(*t_)); > 113 int x_[] = ; > 114 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 115 int C = ; > 116 double _ = ; > 117 END > 118 */ > 119 } > 120 // END CUT HERE
Added SRM/676-U/1B.cpp version [5b1986066a865398]
> 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 int lsb(int x) { > 23 for(int i=0 ;; ++i) > 24 if(x&(1<<i)) > 25 return i; > 26 } > 27 > 28 > 29 class BoardEscape { public: > 30 string findWinner(vector <string> s, int k) > 31 { > 32 const int H = s.size(), W = s[0].size(); > 33 const int dy[] = {-1,+1,0,0}; > 34 const int dx[] = {0,0,-1,+1}; > 35 > 36 vector<vector<vector<int>>> G_history; > 37 for(int t=0; t<=256; ++t) { > 38 vector<vector<int>> G(H, vector<int>(W)); > 39 for(int y=0; y<H; ++y) > 40 for(int x=0; x<W; ++x) if(s[y][x]!='#') { > 41 if(G_history.empty()) > 42 G[y][x] = 0; > 43 else { > 44 if(s[y][x]=='E') > 45 G[y][x] = 0; > 46 else { > 47 int nf = 0xffffffff; > 48 for(int _=0; _<4; ++_) { > 49 int yy=y+dy[_], xx=x+dx[ > 50 if(0<=yy&&yy<H&&0<=xx&&x > 51 nf &= ~(1<<G_his > 52 } > 53 G[y][x] = lsb(nf); > 54 } > 55 } > 56 } > 57 G_history.emplace_back(G); > 58 } > 59 > 60 int ans = 0; > 61 for(int y=0; y<H; ++y) > 62 for(int x=0; x<W; ++x) if(s[y][x]=='T') { > 63 if(k < G_history.size()) > 64 ans ^= G_history[k][y][x]; > 65 else > 66 ans ^= G_history[((k-1)%64)+193][y][x]; > 67 } > 68 return (ans ? "Alice" : "Bob"); > 69 } > 70 }; > 71 > 72 // BEGIN CUT HERE > 73 #include <ctime> > 74 double start_time; string timer() > 75 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 76 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 77 { os << "{ "; > 78 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 79 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 80 void verify_case(const string& Expected, const string& Received) { > 81 bool ok = (Expected == Received); > 82 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 83 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 84 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 85 #define END verify_case(_, BoardEscape().findWinner(s, k));} > 86 int main(){ > 87 CASE(0) > 88 string s_[] = {"TE"}; > 89 vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 90 int k = 2; > 91 string _ = "Alice"; > 92 END > 93 CASE(1) > 94 string s_[] = {"E#E", > 95 "#T#", > 96 "E#E"}; > 97 vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 98 int k = 1000000; > 99 string _ = "Bob"; > 100 END > 101 CASE(2) > 102 string s_[] = {"T.T.T.", > 103 ".E.E.E"}; > 104 vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 105 int k = 1; > 106 string _ = "Alice"; > 107 END > 108 CASE(3) > 109 string s_[] = {"TTE"}; > 110 vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 111 int k = 6; > 112 string _ = "Alice"; > 113 END > 114 CASE(4) > 115 string s_[] = {"..........................", > 116 "......TTT..TTT..T...T.....", > 117 ".....T.....T..T.TT.TT.....", > 118 "......TTT..TTT..T.T.T.....", > 119 ".........T.T.T..T...T.....", > 120 "......TTT..T..T.T...T.....", > 121 "..........................", > 122 "...E#E#E#E#E#E#E#E#E#E#...", > 123 "..........................", > 124 "......TTT..TTT...TTT......", > 125 ".....T........T.T.........", > 126 "......TTT.....T..TTT......", > 127 ".....T...T...T..T...T.....", > 128 "......TTT....T...TTT......", > 129 "..........................", > 130 "...#E#E#E#E#E#E#E#E#E#E...", > 131 "..........................", > 132 "....TT...T...T..T.TTT.T...", > 133 "...T.....T...T..T.T...T...", > 134 "...T.TT..T...TTTT.TT..T...", > 135 "...T..T..T...T..T.T.......", > 136 "....TT...TTT.T..T.T...T...", > 137 ".........................."}; > 138 vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 139 int k = 987654321; > 140 string _ = "Bob"; > 141 END > 142 /* > 143 CASE(5) > 144 string s_[] = ; > 145 vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 146 int k = ; > 147 string _ = ; > 148 END > 149 CASE(6) > 150 string s_[] = ; > 151 vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 152 int k = ; > 153 string _ = ; > 154 END > 155 */ > 156 } > 157 // END CUT HERE