Overview
| SHA1 Hash: | ed7454da2aeff4d67d8a505ef2c33d08e508dedf |
|---|---|
| Date: | 2016-10-26 12:37:23 |
| User: | kinaba |
| Comment: | 701 |
| 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/701-U/1A.cpp version [5e98535c0578c879]
> 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 PartisanGame { public: > 23 string getWinner(int n, vector <int> a, vector <int> b) > 24 { > 25 return firstPlayerWin(n, a, b) ? "Alice" : "Bob"; > 26 } > 27 > 28 bool firstPlayerWin(int n, const vector<int>& a, const vector<int>& b) { > 29 vector<int> aw_bw; > 30 aw_bw.push_back(0*2 + 0); > 31 > 32 for (int k = 1; k <= 2000; ++k) { > 33 int aw = 0; > 34 for (int ai : a) > 35 if (k - ai >= 0 && (aw_bw[k - ai] & 1) == 0) > 36 aw = 1; > 37 int bw = 0; > 38 for (int bi : b) > 39 if (k - bi >= 0 && (aw_bw[k - bi] & 2) == 0) > 40 bw = 1; > 41 aw_bw.push_back(aw * 2 + bw); > 42 } > 43 if (n < aw_bw.size()) { > 44 return (aw_bw[n] & 2) != 0; > 45 } > 46 > 47 int z = int(aw_bw.size()) - 5; > 48 for (int t = z - 1;; --t) { > 49 if (equal(aw_bw.begin() + t, aw_bw.begin() + t + 5, aw_b > 50 n = (n - t) % (z - t) + t; > 51 return (aw_bw[n] & 2) != 0; > 52 } > 53 } > 54 assert(false); > 55 } > 56 }; > 57 > 58 // BEGIN CUT HERE > 59 #include <ctime> > 60 double start_time; string timer() > 61 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 62 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 63 { os << "{ "; > 64 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 65 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 66 void verify_case(const string& Expected, const string& Received) { > 67 bool ok = (Expected == Received); > 68 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 69 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 70 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 71 #define END verify_case(_, PartisanGame().getWinner(n, a, b));} > 72 int main(){ > 73 > 74 CASE(0) > 75 int n = 7; > 76 int a_[] = {3, 4}; > 77 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 78 int b_[] = {4}; > 79 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 80 string _ = "Alice"; > 81 END > 82 CASE(1) > 83 int n = 10; > 84 int a_[] = {1}; > 85 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 86 int b_[] = {4, 3, 2}; > 87 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 88 string _ = "Bob"; > 89 END > 90 CASE(2) > 91 int n = 104982; > 92 int a_[] = {2, 3, 4, 5}; > 93 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 94 int b_[] = {2, 5}; > 95 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 96 string _ = "Alice"; > 97 END > 98 CASE(3) > 99 int n = 999999999; > 100 int a_[] = {4}; > 101 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 102 int b_[] = {5}; > 103 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 104 string _ = "Bob"; > 105 END > 106 CASE(4) > 107 int n = 1000000000; > 108 int a_[] = {1,2,3,4,5}; > 109 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 110 int b_[] = {1,2,3,4,5}; > 111 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 112 string _ = "Alice"; > 113 END > 114 CASE(5) > 115 int n = 0; > 116 int a_[] = { 1 }; > 117 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 118 int b_[] = { 1 }; > 119 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 120 string _ = "Bob"; > 121 END > 122 CASE(6) > 123 int n = 1; > 124 int a_[] = { 2,3,4 }; > 125 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 126 int b_[] = { 2 }; > 127 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 128 string _ = "Bob"; > 129 END > 130 } > 131 // END CUT HERE
Added SRM/701-U/1B.cpp version [3d1ad8a36cc1d497]
> 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 string S; > 23 > 24 class KthStringAgain { > 25 public: > 26 struct Cand { > 27 // represents ALL(S[perm_head..$]) S[tail_mask]^r > 28 int perm_head; > 29 string tail; > 30 LL num; > 31 Cand(int p, const string& t, LL n=1) : perm_head(p), tail(t), nu > 32 LL count() const { return (1LL << (S.size() - perm_head))*num; } > 33 > 34 bool operator<(const Cand& rhs) const { > 35 if (perm_head != rhs.perm_head) return perm_head < rhs.p > 36 return tail < rhs.tail; > 37 } > 38 bool operator==(const Cand& rhs) const { > 39 if (perm_head != rhs.perm_head) return false; > 40 return tail == rhs.tail; > 41 } > 42 }; > 43 > 44 string getKth(string s, long long k) { > 45 S = s; > 46 vector<Cand> cc(1, Cand(0, string())); > 47 return findKthAmong(cc, k - 1); > 48 } > 49 > 50 string findKthAmong(vector<Cand>& c, LL k) { > 51 sort(c.begin(), c.end()); > 52 for(int i=c.size()-1; i>=1; --i) > 53 if (c[i] == c[i - 1]) { > 54 c[i - 1].num += c[i].num; > 55 c[i].num = 0; > 56 } > 57 > 58 map<char, vector<Cand>> next; > 59 for (const Cand& cc : c) { > 60 if (cc.num == 0) > 61 continue; > 62 > 63 if (cc.perm_head == S.size()) { > 64 if (cc.tail.empty()) > 65 return ""; //? > 66 > 67 next[cc.tail[0]].emplace_back(cc.perm_head, cc.t > 68 } > 69 else { > 70 for (int i = cc.perm_head; i < S.size(); ++i) { > 71 string t2 = S.substr(cc.perm_head, i - c > 72 reverse(t2.begin(), t2.end()); > 73 t2 += cc.tail; > 74 next[S[i]].emplace_back(i + 1, t2, cc.nu > 75 } > 76 } > 77 } > 78 > 79 LL off = 0; > 80 for (auto&& kv : next) { > 81 LL num = 0; > 82 for (auto&& vv : kv.second) > 83 num += vv.count(); > 84 if (off <= k && k < off + num) { > 85 return kv.first + findKthAmong(kv.second, k - of > 86 } > 87 off += num; > 88 } > 89 assert(false); > 90 return "WRONG ANSWER"; > 91 } > 92 }; > 93 > 94 // BEGIN CUT HERE > 95 #include <ctime> > 96 double start_time; string timer() > 97 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 98 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 99 { os << "{ "; > 100 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 101 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 102 void verify_case(const string& Expected, const string& Received) { > 103 bool ok = (Expected == Received); > 104 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 105 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 106 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 107 #define END verify_case(_, KthStringAgain().getKth(s, k));} > 108 int main(){ > 109 > 110 CASE(0) > 111 string s = "xyz"; > 112 long long k = 5LL; > 113 string _ = "yzx"; > 114 END > 115 CASE(1) > 116 string s = "abc"; > 117 long long k = 1LL; > 118 string _ = "abc"; > 119 END > 120 CASE(2) > 121 string s = "abc"; > 122 long long k = 8LL; > 123 string _ = "cba"; > 124 END > 125 CASE(3) > 126 string s = "topcoder"; > 127 long long k = 58LL; > 128 string _ = "ooredcpt"; > 129 END > 130 CASE(4) > 131 string s = "aaaabcdeeeghhhhhiijjjkllmmooooqqrrrrssttuuvvvvvwyy"; > 132 long long k = 38517901796974LL; > 133 string _ = "aaaacdeehhhijklmmqqrsttvvvvwyyvuusrrrooooljjihhgeb"; > 134 END > 135 CASE(5) > 136 string s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"; > 137 long long k = 1234567890LL; > 138 string _ = "???????"; > 139 END > 140 /* > 141 CASE(6) > 142 string s = ; > 143 long long k = LL; > 144 string _ = ; > 145 END > 146 */ > 147 } > 148 // END CUT HERE
Added SRM/701-U/1C-U.cpp version [db64e8ad7fab54e4]
> 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 static const unsigned MODVAL = 1000000007; > 23 struct mint > 24 { > 25 unsigned val; > 26 mint() :val(0) {} > 27 mint(int x) :val(x%MODVAL) {} > 28 mint(unsigned 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 operator+(mint x, mint y) { return x += y; } > 35 mint operator-(mint x, mint y) { return x -= y; } > 36 mint operator*(mint x, mint y) { return x *= y; } > 37 > 38 mint POW(mint x, LL e) { mint v = 1; for (; e; x *= x, e >>= 1) if (e & 1) v *= > 39 mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL - 2); } > 40 mint operator/(mint x, mint y) { return x /= y; } > 41 > 42 vector<mint> FAC_(1, 1); > 43 mint FAC(LL n) { while (FAC_.size() <= n) FAC_.push_back(FAC_.back()*LL(FAC_.siz > 44 > 45 // nCk :: O(log MODVAL) time, O(n) space. > 46 mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n - k)); } > 47 > 48 class FibonacciStringSum { public: > 49 int get(int n, int a, int b) > 50 { > 51 mint total = 0; > 52 for (int n0 = 0; n0 <= n; ++n0) { > 53 int n1 = n - n0; > 54 if(n1 <= n0+1) > 55 total += POW(n0, a) * POW(n1, b) * num(n0, n1); > 56 } > 57 return total.val; > 58 } > 59 > 60 mint num(int n0, int n1) > 61 { > 62 if (n1 == 0) > 63 return 1; > 64 > 65 mint all = 0; > 66 // [10] [0] pat > 67 if (n1 <= n0) { > 68 all += C(n1 + (n0 - n1), n1); > 69 } > 70 // [10] [0] 1 pat > 71 all += C(n1 - 1 + (n0 - n1 + 1), n1 - 1); > 72 return all; > 73 } > 74 }; > 75 > 76 // BEGIN CUT HERE > 77 #include <ctime> > 78 double start_time; string timer() > 79 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 80 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 81 { os << "{ "; > 82 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 83 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 84 void verify_case(const int& Expected, const int& Received) { > 85 bool ok = (Expected == Received); > 86 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 87 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 88 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 89 #define END verify_case(_, FibonacciStringSum().get(n, a, b));} > 90 int main(){ > 91 > 92 CASE(0) > 93 int n = 3; > 94 int a = 0; > 95 int b = 0; > 96 int _ = 5; > 97 END > 98 CASE(1) > 99 int n = 3; > 100 int a = 0; > 101 int b = 1; > 102 int _ = 5; > 103 END > 104 CASE(2) > 105 int n = 10; > 106 int a = 10; > 107 int b = 10; > 108 int _ = 518500021; > 109 END > 110 CASE(3) > 111 int n = 5000; > 112 int a = 20; > 113 int b = 20; > 114 int _ = 880245669; > 115 END > 116 /* > 117 CASE(4) > 118 int n = ; > 119 int a = ; > 120 int b = ; > 121 int _ = ; > 122 END > 123 CASE(5) > 124 int n = ; > 125 int a = ; > 126 int b = ; > 127 int _ = ; > 128 END > 129 */ > 130 } > 131 // END CUT HERE
Modified TZTesterSp/template.cpp from [6e30a998ce576012] to [f84e3f16d60fb246].
10 #include <iterator> 10 #include <iterator> 11 #include <functional> 11 #include <functional> 12 #include <complex> 12 #include <complex> 13 #include <queue> 13 #include <queue> 14 #include <stack> 14 #include <stack> 15 #include <cmath> 15 #include <cmath> 16 #include <cassert> 16 #include <cassert> > 17 #include <tuple> 17 using namespace std; 18 using namespace std; 18 typedef long long LL; 19 typedef long long LL; 19 typedef long double LD; < 20 typedef complex<LD> CMP; | 20 typedef complex<double> CMP; 21 21 22 class $CLASSNAME$ { public: 22 class $CLASSNAME$ { public: 23 $RC$ $METHODNAME$($METHODPARMS$) 23 $RC$ $METHODNAME$($METHODPARMS$) 24 { 24 { 25 } 25 } 26 }; 26 }; 27 27 28 $TESTCODE$ 28 $TESTCODE$