Overview
| SHA1 Hash: | ea99443fa254934f4e6ebe43de42584c1ba44e9f |
|---|---|
| Date: | 2014-06-07 14:12:27 |
| User: | kinaba |
| Comment: | 623 |
| 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/623-U/1A.cpp version [5a7a82e56d0038ed]
> 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 UniformBoard { public: > 23 int getBoard(vector <string> board, int K) > 24 { > 25 const int N = board.size(); > 26 > 27 int A=0, P=0; > 28 for(int y=0; y<N; ++y) > 29 for(int x=0; x<N; ++x) { > 30 if(board[y][x]=='P')++P; > 31 if(board[y][x]=='A')++A; > 32 } > 33 > 34 int best = 0; > 35 for(int y=0; y<N; ++y) > 36 for(int x=0; x<N; ++x) > 37 for(int yy=y+1; yy<=N; ++yy) > 38 for(int xx=x+1; xx<=N; ++xx) > 39 { > 40 int a=0, p=0; > 41 for(int i=y; i<yy; ++i) > 42 for(int k=x; k<xx; ++k) { > 43 if(board[i][k]=='P')++p; > 44 if(board[i][k]=='A')++a; > 45 } > 46 int move = calc(A,P,N*N-A-P,a,p,(yy-y)*(xx-x)-a-p); > 47 if(move<=K) > 48 best = max(best, (yy-y)*(xx-x)); > 49 } > 50 return best; > 51 } > 52 > 53 int calc(int A, int P, int E, int a, int p, int e) > 54 { > 55 const int INF = 0x7ffffff; > 56 A -= a; > 57 P -= p; > 58 E -= e; > 59 > 60 if(e+p > A) > 61 return INF; > 62 > 63 int move = 0; > 64 if(e) { > 65 move += e; > 66 E += e; > 67 A -= e; > 68 a += e; > 69 e = 0; > 70 } > 71 if(p) { > 72 if(E == 0) > 73 return INF; > 74 move += 2*p; > 75 } > 76 return move; > 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(_, UniformBoard().getBoard(board, K));} > 94 int main(){ > 95 > 96 CASE(0) > 97 string board_[] = {"AP", > 98 ".A"}; > 99 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 100 int K = 0; > 101 int _ = 1; > 102 END > 103 CASE(1) > 104 string board_[] = {"AP", > 105 ".A"}; > 106 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 107 int K = 1; > 108 int _ = 2; > 109 END > 110 CASE(2) > 111 string board_[] = {"PPP", > 112 "APA", > 113 "A.P"}; > 114 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 115 int K = 2; > 116 int _ = 3; > 117 END > 118 CASE(3) > 119 string board_[] = {"AAA", > 120 "PPP", > 121 "AAA"}; > 122 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 123 int K = 10; > 124 int _ = 3; > 125 END > 126 CASE(4) > 127 string board_[] = {"."}; > 128 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 129 int K = 1000; > 130 int _ = 0; > 131 END > 132 CASE(5) > 133 string board_[] = {"PPAAPA..AP", > 134 "PPA.APAP..", > 135 "..P.AA.PPP", > 136 "P.P..APAA.", > 137 "P.P..P.APA", > 138 "PPA..AP.AA", > 139 "APP..AAPAA", > 140 "P.P.AP...P", > 141 ".P.A.PAPPA", > 142 "..PAPAP..P"}; > 143 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 144 int K = 10; > 145 int _ = 15; > 146 END > 147 /* > 148 CASE(6) > 149 string board_[] = ; > 150 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 151 int K = ; > 152 int _ = ; > 153 END > 154 CASE(7) > 155 string board_[] = ; > 156 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 157 int K = ; > 158 int _ = ; > 159 END > 160 */ > 161 } > 162 // END CUT HERE
Added SRM/623-U/1B-U.cpp version [328f1d8dd94187c9]
> 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 CatchTheBeat { public: > 23 int maxCatched(int n, int x0, int y0, int a, int b, int c, int d, int mo > 24 { > 25 vector<int> x(n), y(n); > 26 x[0] = x0; > 27 for(int i=1; i<n; ++i) > 28 x[i] = int((LL(x[i-1]) * a + b) % mod1); > 29 for(int i=0; i<n; ++i) > 30 x[i] = x[i] - offset; > 31 > 32 y[0] = y0; > 33 for(int i=1; i<n; ++i) > 34 y[i] = int((LL(y[i-1]) * c + d) % mod2); > 35 > 36 return solve(n, x, y); > 37 } > 38 > 39 int solve(int N, const vector<int>& x, const vector<int>& y) > 40 { > 41 vector<pair<int,int>> tx; > 42 for(int i=0; i<N; ++i) > 43 tx.emplace_back(y[i], x[i]); > 44 tx.emplace_back(0, 0); > 45 sort(tx.begin(), tx.end()); > 46 > 47 vector<vector<int>> score_table(tx.size()); > 48 score_table[0].push_back(0); > 49 int best_score = 0; > 50 for(int c=1; c<tx.size(); ++c) > 51 { > 52 int pre = -1; > 53 for(int bs=best_score; bs>=0; --bs) { > 54 for(int p: score_table[bs]) > 55 if(tx[c].first - tx[p].first >= abs(tx[ > 56 {pre = bs; goto found_pre;} > 57 } > 58 found_pre: > 59 if(pre>=0) { > 60 score_table[pre+1].push_back(c); > 61 best_score = max(best_score, pre+1); > 62 } > 63 } > 64 return best_score; > 65 } > 66 }; > 67 > 68 // BEGIN CUT HERE > 69 #include <ctime> > 70 double start_time; string timer() > 71 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 72 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 73 { os << "{ "; > 74 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 75 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 76 void verify_case(const int& Expected, const int& Received) { > 77 bool ok = (Expected == Received); > 78 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 79 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 80 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 81 #define END verify_case(_, CatchTheBeat().maxCatched(n, x0, y0, a, b, c, d, > 82 int main(){ > 83 > 84 CASE(0) > 85 int n = 3; > 86 int x0 = 0; > 87 int y0 = 0; > 88 int a = 1; > 89 int b = 1; > 90 int c = 1; > 91 int d = 1; > 92 int mod1 = 100; > 93 int mod2 = 100; > 94 int offset = 1; > 95 int _ = 2; > 96 END > 97 CASE(1) > 98 int n = 1; > 99 int x0 = 0; > 100 int y0 = 1234; > 101 int a = 0; > 102 int b = 0; > 103 int c = 0; > 104 int d = 0; > 105 int mod1 = 1000000000; > 106 int mod2 = 1000000000; > 107 int offset = 1000; > 108 int _ = 1; > 109 END > 110 CASE(2) > 111 int n = 1; > 112 int x0 = 0; > 113 int y0 = 999; > 114 int a = 0; > 115 int b = 0; > 116 int c = 0; > 117 int d = 0; > 118 int mod1 = 1000000000; > 119 int mod2 = 1000000000; > 120 int offset = 1000; > 121 int _ = 0; > 122 END > 123 CASE(3) > 124 int n = 100; > 125 int x0 = 0; > 126 int y0 = 0; > 127 int a = 1; > 128 int b = 1; > 129 int c = 1; > 130 int d = 1; > 131 int mod1 = 3; > 132 int mod2 = 58585858; > 133 int offset = 1; > 134 int _ = 66; > 135 END > 136 CASE(4) > 137 int n = 500000; > 138 int x0 = 123456; > 139 int y0 = 0; > 140 int a = 1; > 141 int b = 0; > 142 int c = 1; > 143 int d = 1; > 144 int mod1 = 1000000000; > 145 int mod2 = 1000000000; > 146 int offset = 0; > 147 int _ = 376544; > 148 END > 149 CASE(5) > 150 int n = 500000; > 151 int x0 = 0; > 152 int y0 = 0; > 153 int a = 0; > 154 int b = 0; > 155 int c = 0; > 156 int d = 0; > 157 int mod1 = 1; > 158 int mod2 = 1; > 159 int offset = 0; > 160 int _ = 500000; > 161 END > 162 CASE(6) > 163 int n = 10; > 164 int x0 = 999999957; > 165 int y0 = 79; > 166 int a = 993948167; > 167 int b = 24597383; > 168 int c = 212151897; > 169 int d = 999940854; > 170 int mod1 = 999999986; > 171 int mod2 = 999940855; > 172 int offset = 3404; > 173 int _ = 3; > 174 END > 175 /* > 176 CASE(7) > 177 int n = ; > 178 int x0 = ; > 179 int y0 = ; > 180 int a = ; > 181 int b = ; > 182 int c = ; > 183 int d = ; > 184 int mod1 = ; > 185 int mod2 = ; > 186 int offset = ; > 187 int _ = ; > 188 END > 189 CASE(8) > 190 int n = ; > 191 int x0 = ; > 192 int y0 = ; > 193 int a = ; > 194 int b = ; > 195 int c = ; > 196 int d = ; > 197 int mod1 = ; > 198 int mod2 = ; > 199 int offset = ; > 200 int _ = ; > 201 END > 202 */ > 203 } > 204 // END CUT HERE
Added SRM/623-U/1C-U.cpp version [2ec89edcc9c2afbe]
> 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 AliceAndFriends { public: > 23 double getMoney(vector <int> cards) > 24 { > 25 int N = cards.size(); > 26 double ex = 0.0; > 27 for(int alice=0; alice<N; ++alice) > 28 { > 29 double best = -1e+300; > 30 > 31 int R = cards[alice]; > 32 for(int B=0; B<=R; ++B) > 33 { > 34 double total_gain = 0.0; > 35 for(int i=0; i<N; ++i) if(i!=alice) > 36 { > 37 int r = cards[i]; > 38 double best_you = 1e+300; > 39 int b; > 40 if(R==r) > 41 b = B; > 42 else if(R < r) > 43 b = 0; > 44 else { > 45 } > 46 > 47 // r-b > R-B > 48 // r-b > R+B > 49 // r+b > R-B > 50 // r+b > R+B > 51 // ができるだけ成り立ちたい > 52 for(int b=0; b<=r; ++b) > 53 { > 54 // Alice: [R-B or R+B] > 55 // You: [r-b or r+b] > 56 double s = 0.0; > 57 s += (r-b<R-B ? +0.25 : r-b>R-B > 58 s += (r-b<R+B ? +0.25 : r-b>R+B > 59 s += (r+b<R-B ? +0.25 : r+b>R-B > 60 s += (r+b<R+B ? +0.25 : r+b>R+B > 61 best_you = min(best_you, s); > 62 } > 63 total_gain += best_you; > 64 } > 65 best = max(best, total_gain); > 66 } > 67 ex += best; > 68 } > 69 return ex / N; > 70 } > 71 }; > 72 > 73 // BEGIN CUT HERE > 74 #include <ctime> > 75 double start_time; string timer() > 76 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 77 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 78 { os << "{ "; > 79 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 80 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 81 void verify_case(const double& Expected, const double& Received) { > 82 bool ok = (abs(Expected - Received) < 1e-9); > 83 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 84 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 85 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 86 #define END verify_case(_, AliceAndFriends().getMoney(cards));} > 87 int main(){ > 88 > 89 CASE(0) > 90 int cards_[] = {10, 1}; > 91 vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); > 92 double _ = 0.0; > 93 END > 94 CASE(1) > 95 int cards_[] = {10, 9}; > 96 vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); > 97 double _ = -0.25; > 98 END > 99 CASE(2) > 100 int cards_[] = {1, 3}; > 101 vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); > 102 double _ = 0.0; > 103 END > 104 CASE(3) > 105 int cards_[] = {1000000000, 1000000000}; > 106 vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); > 107 double _ = 0.0; > 108 END > 109 CASE(4) > 110 int cards_[] = {42, 468, 335, 501, 170, 725, 479, 359, 963, 465, 706, 14 > 111 943, 828, 437, 392, 605, 903, 154, 293, 383, 422, 717, 719, 896, 448, 727, 772, > 112 870, 913, 668, 300, 36, 895, 704, 812, 323, 334, 674, 665, 142, 712, 254, 869}; > 113 vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); > 114 double _ = -9.095; > 115 END > 116 /* > 117 CASE(5) > 118 int cards_[] = ; > 119 vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); > 120 double _ = ; > 121 END > 122 CASE(6) > 123 int cards_[] = ; > 124 vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_)); > 125 double _ = ; > 126 END > 127 */ > 128 } > 129 // END CUT HERE