Overview
| SHA1 Hash: | d47754550521bb6b955b03563d405feb308a80b9 |
|---|---|
| Date: | 2016-01-13 03:42:12 |
| User: | kinaba |
| Comment: | 678 |
| 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/678-U/1A.cpp version [52600c1b1ddbdd87]
> 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 ANewHope { public: > 23 int count(vector <int> firstWeek, vector <int> lastWeek, int D) > 24 { > 25 const int N = firstWeek.size(); > 26 const int s = N-D; > 27 int worst = 0; > 28 for(int v=1; v<=N; ++v) { > 29 int a = find(firstWeek.begin(), firstWeek.end(), v) - fi > 30 int b = find(lastWeek.begin(), lastWeek.end(), v) - last > 31 worst = max(worst, b==a ? 0 : b>a ? 1 : (a-b+s-1)/s); > 32 } > 33 return worst+1; > 34 } > 35 }; > 36 > 37 // BEGIN CUT HERE > 38 #include <ctime> > 39 double start_time; string timer() > 40 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 41 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 42 { os << "{ "; > 43 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 44 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 45 void verify_case(const int& Expected, const int& Received) { > 46 bool ok = (Expected == Received); > 47 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 48 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 49 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 50 #define END verify_case(_, ANewHope().count(firstWeek, lastWeek, D));} > 51 int main(){ > 52 > 53 CASE(0) > 54 int firstWeek_[] = {1,2,3,4}; > 55 vector <int> firstWeek(firstWeek_, firstWeek_+sizeof(firstWeek_)/sizeo > 56 int lastWeek_[] = {4,3,2,1}; > 57 vector <int> lastWeek(lastWeek_, lastWeek_+sizeof(lastWeek_)/sizeof(*l > 58 int D = 3; > 59 int _ = 4; > 60 END > 61 CASE(1) > 62 int firstWeek_[] = {8,5,4,1,7,6,3,2}; > 63 vector <int> firstWeek(firstWeek_, firstWeek_+sizeof(firstWeek_)/sizeo > 64 int lastWeek_[] = {2,4,6,8,1,3,5,7}; > 65 vector <int> lastWeek(lastWeek_, lastWeek_+sizeof(lastWeek_)/sizeof(*l > 66 int D = 3; > 67 int _ = 3; > 68 END > 69 CASE(2) > 70 int firstWeek_[] = {1,2,3,4}; > 71 vector <int> firstWeek(firstWeek_, firstWeek_+sizeof(firstWeek_)/sizeo > 72 int lastWeek_[] = {1,2,3,4}; > 73 vector <int> lastWeek(lastWeek_, lastWeek_+sizeof(lastWeek_)/sizeof(*l > 74 int D = 2; > 75 int _ = 1; > 76 END > 77 /* > 78 CASE(3) > 79 int firstWeek_[] = ; > 80 vector <int> firstWeek(firstWeek_, firstWeek_+sizeof(firstWeek_)/sizeo > 81 int lastWeek_[] = ; > 82 vector <int> lastWeek(lastWeek_, lastWeek_+sizeof(lastWeek_)/sizeof(*l > 83 int D = ; > 84 int _ = ; > 85 END > 86 CASE(4) > 87 int firstWeek_[] = ; > 88 vector <int> firstWeek(firstWeek_, firstWeek_+sizeof(firstWeek_)/sizeo > 89 int lastWeek_[] = ; > 90 vector <int> lastWeek(lastWeek_, lastWeek_+sizeof(lastWeek_)/sizeof(*l > 91 int D = ; > 92 int _ = ; > 93 END > 94 */ > 95 } > 96 // END CUT HERE
Added SRM/678-U/1B.cpp version [01e65b483160dba9]
> 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 TheEmpireStrikesBack { public: > 23 int find(int AX, int BX, int CX, int AY, int BY, int CY, int N, int M) > 24 { > 25 vector<pair<int,int>> P(N); > 26 P[0].first = AX; > 27 P[0].second = AY; > 28 for(int i=1; i<N; ++i) { > 29 P[i].first = int((LL(P[i-1].first) * BX + CX) % 10000000 > 30 P[i].second = int((LL(P[i-1].second) * BY + CY) % 100000 > 31 } > 32 > 33 // Sort: Large Y first, Large X first > 34 sort(P.begin(), P.end(), [&](const pair<int,int>& lhs, const pai > 35 if(lhs.second == rhs.second) return lhs.first > rhs.firs > 36 return lhs.second > rhs.second; > 37 }); > 38 > 39 // Border stars, worth targetting. > 40 vector<pair<int,int>> B; > 41 for(auto& p: P) > 42 if(B.empty() || B.back().first < p.first) > 43 B.push_back(p); > 44 > 45 int L=-1, R=1000000007; // (L,R] > 46 while(R-L>1) { > 47 int C = (L+R)/2; > 48 (least_missile_to_destory_all(B, C)<=M ? R : L) = C; > 49 } > 50 return R; > 51 } > 52 > 53 int least_missile_to_destory_all(const vector<pair<int,int>>& B, int T) > 54 { > 55 // Greedy. > 56 int count = 0; > 57 for(int to_cover=0; to_cover<B.size(); ) { > 58 int missile = to_cover; > 59 for(; missile<B.size(); ++missile) > 60 if(B[missile].first+T < B[to_cover].first || B[m > 61 break; > 62 --missile; > 63 ++count; > 64 for(; to_cover<B.size(); ++to_cover) > 65 if(B[missile].first+T < B[to_cover].first || B[m > 66 break; > 67 } > 68 return count; > 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 int& Expected, const int& 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(_, TheEmpireStrikesBack().find(AX, BX, CX, AY, BY, > 86 int main(){ > 87 > 88 CASE(0) > 89 int AX = 2; > 90 int BX = 2; > 91 int CX = 2; > 92 int AY = 2; > 93 int BY = 2; > 94 int CY = 2; > 95 int N = 2; > 96 int M = 1; > 97 int _ = 0; > 98 END > 99 CASE(1) > 100 int AX = 2; > 101 int BX = 2; > 102 int CX = 2; > 103 int AY = 2; > 104 int BY = 4; > 105 int CY = 1000000000; > 106 int N = 2; > 107 int M = 1; > 108 int _ = 1; > 109 END > 110 CASE(2) > 111 int AX = 1; > 112 int BX = 3; > 113 int CX = 8; > 114 int AY = 10000; > 115 int BY = 10; > 116 int CY = 999910000; > 117 int N = 3; > 118 int M = 1; > 119 int _ = 30; > 120 END > 121 CASE(3) > 122 int AX = 0; > 123 int BX = 0; > 124 int CX = 0; > 125 int AY = 0; > 126 int BY = 0; > 127 int CY = 0; > 128 int N = 100000; > 129 int M = 1000; > 130 int _ = 0; > 131 END > 132 CASE(4) > 133 int AX = 10; > 134 int BX = 20; > 135 int CX = 30; > 136 int AY = 40; > 137 int BY = 50; > 138 int CY = 60; > 139 int N = 100000; > 140 int M = 10; > 141 int _ = 15720; > 142 END > 143 /* > 144 CASE(5) > 145 int AX = ; > 146 int BX = ; > 147 int CX = ; > 148 int AY = ; > 149 int BY = ; > 150 int CY = ; > 151 int N = ; > 152 int M = ; > 153 int _ = ; > 154 END > 155 CASE(6) > 156 int AX = ; > 157 int BX = ; > 158 int CX = ; > 159 int AY = ; > 160 int BY = ; > 161 int CY = ; > 162 int N = ; > 163 int M = ; > 164 int _ = ; > 165 END > 166 */ > 167 } > 168 // END CUT HERE
Added SRM/678-U/1C-U.cpp version [1517aa3e89cb81aa]
> 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 ReturnOfTheJedi { public: > 23 vector <double> minimalExpectation(vector <int> x, vector <int> p) > 24 { > 25 vector<pair<double,double>> item; > 26 for(int i=0; i<x.size(); ++i) > 27 item.emplace_back(p[i]/100000.0, x[i]); > 28 > 29 vector<double> ans(x.size()); > 30 > 31 vector<pair<double,double>> iA = item; > 32 double pA = 1.0; > 33 double xA = 0.0; > 34 vector<pair<double,double>> iB = item; > 35 double pB = 1.0; > 36 double xB = 0.0; > 37 { > 38 vector<pair<double,double>>::iterator b1 = iB.begin(); > 39 double best_score = 1e+300; > 40 for(vector<pair<double,double>>::iterator it = iB.begin( > 41 double score = it->first * it->second; > 42 if(best_score > score) > 43 {b1 = it, best_score = score;} > 44 } > 45 pB = b1->first; > 46 xB = b1->second; > 47 iB.erase(b1); > 48 ans[0] = (pB*xB); > 49 } > 50 > 51 for(int k=1; k<ans.size(); ++k) { > 52 vector<pair<double,double>>::iterator b1 = iB.begin(); > 53 double best_score = 1e+300; > 54 for(vector<pair<double,double>>::iterator it = iB.begin( > 55 double score = pB*it->first * (xB+it->second); > 56 if(best_score > score) > 57 {b1 = it, best_score = score;} > 58 } > 59 vector<pair<double,double>>::iterator b2 = iA.begin(); > 60 vector<pair<double,double>>::iterator b3 = iA.begin(); > 61 bool A_mode = false; > 62 for(vector<pair<double,double>>::iterator it = iA.begin( > 63 for(vector<pair<double,double>>::iterator kt = it; kt != > 64 double score = pA*it->first*kt->first * (xA+it-> > 65 if(best_score > score) > 66 {b2 = it, b3 = kt, best_score = score, A > 67 } > 68 if(!A_mode) { > 69 pA = pB; > 70 xA = xB; > 71 iA = iB; > 72 pB *= b1->first; > 73 xB += b1->second; > 74 iB.erase(b1); > 75 } else { > 76 pA *= b2->first * b3->first; > 77 xA += b2->second + b3->second; > 78 auto xxx = *b3; > 79 iA.erase(b2); > 80 iA.erase(std::find(iA.begin(), iA.end(), xxx)); > 81 swap(pA, pB); > 82 swap(xA, xB); > 83 swap(iA, iB); > 84 } > 85 ans[k] = pB*xB; > 86 } > 87 return ans; > 88 } > 89 }; > 90 > 91 // BEGIN CUT HERE > 92 #include <ctime> > 93 double start_time; string timer() > 94 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 95 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 96 { os << "{ "; > 97 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 98 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 99 void verify_case(const vector <double>& Expected, const vector <double>& Receive > 100 bool ok = true; > 101 for(int i=0; i<Expected.size(); ++i) > 102 if( abs(Expected[i]-Received[i]) >= 1e-9 ) > 103 ok = false; > 104 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 105 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 106 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 107 #define END verify_case(_, ReturnOfTheJedi().minimalExpectation(x, p));} > 108 int main(){ > 109 > 110 CASE(0) > 111 int x_[] = {100,200,300}; > 112 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 113 int p_[] = {50000, 20000, 20000}; > 114 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 115 double __[] = {40.0, 20.000000000000004, 12.000000000000002 }; > 116 vector <double> _(__, __+sizeof(__)/sizeof(*__)); > 117 END > 118 CASE(1) > 119 int x_[] = {200,100,500,300,400}; > 120 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 121 int p_[] = {100000, 100000, 100000, 100000, 100000}; > 122 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 123 double __[] = {100.0, 300.0, 600.0, 1000.0, 1500.0 }; > 124 vector <double> _(__, __+sizeof(__)/sizeof(*__)); > 125 END > 126 CASE(2) > 127 int x_[] = {2,2,100,100}; > 128 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 129 int p_[] = {100000,100000,10000,10000}; > 130 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 131 double __[] = {2.0, 2.0000000000000004, 2.0200000000000005, 2.0400000000 > 132 vector <double> _(__, __+sizeof(__)/sizeof(*__)); > 133 END > 134 CASE(3) > 135 int x_[] = {1,1,200,200}; > 136 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 137 int p_[] = {100000,100000,10000,10000}; > 138 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 139 double __[] = {1.0, 2.0, 4.010000000000001, 4.0200000000000005 }; > 140 vector <double> _(__, __+sizeof(__)/sizeof(*__)); > 141 END > 142 CASE(4) > 143 int x_[] = {1000000000,1000000000,1000000000,1000000000,1000000000,10000 > 144 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 145 int p_[] = {90000,90000,90000,90000,90000,90000,90000,90000,90000,90000} > 146 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 147 double __[] = {9.0E8, 1.62E9, 2.1870000000000005E9, 2.6244000000000005E9 > 148 vector <double> _(__, __+sizeof(__)/sizeof(*__)); > 149 END > 150 /* > 151 CASE(5) > 152 int x_[] = ; > 153 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 154 int p_[] = ; > 155 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 156 double __[] = ; > 157 vector <double> _(__, __+sizeof(__)/sizeof(*__)); > 158 END > 159 CASE(6) > 160 int x_[] = ; > 161 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 162 int p_[] = ; > 163 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 164 double __[] = ; > 165 vector <double> _(__, __+sizeof(__)/sizeof(*__)); > 166 END > 167 */ > 168 } > 169 // END CUT HERE