Overview
| SHA1 Hash: | a31002ea4701273cc180c0b39ec3fac013d27a39 |
|---|---|
| Date: | 2014-01-30 01:49:51 |
| User: | kinaba |
| Comment: | 605 |
| 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/605-U/1A.cpp version [32cf792066917260]
> 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 AlienAndHamburgers { public: > 23 int getNumber(vector <int> type, vector <int> taste) > 24 { > 25 const int N = type.size(); > 26 > 27 vector<pair<int,int>> taste_type; > 28 for(int i=0; i<N; ++i) > 29 taste_type.emplace_back(taste[i], type[i]); > 30 sort(taste_type.rbegin(), taste_type.rend()); > 31 > 32 int best = 0; > 33 > 34 set<int> Y; > 35 int A = 0; > 36 for(auto& tt: taste_type) { > 37 int ta = tt.first; > 38 int ty = tt.second; > 39 if(ta >= 0 || !Y.count(ty)) { > 40 Y.insert(ty); > 41 A += ta; > 42 } > 43 best = max<int>(best, Y.size()*A); > 44 } > 45 > 46 return best; > 47 } > 48 }; > 49 > 50 // BEGIN CUT HERE > 51 #include <ctime> > 52 double start_time; string timer() > 53 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 54 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 55 { os << "{ "; > 56 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 57 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 58 void verify_case(const int& Expected, const int& Received) { > 59 bool ok = (Expected == Received); > 60 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 61 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 62 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 63 #define END verify_case(_, AlienAndHamburgers().getNumber(type, taste));} > 64 int main(){ > 65 > 66 CASE(0) > 67 int type_[] = {1, 2}; > 68 vector <int> type(type_, type_+sizeof(type_)/sizeof(*type_)); > 69 int taste_[] = {4, 7}; > 70 vector <int> taste(taste_, taste_+sizeof(taste_)/sizeof(*taste_)); > 71 int _ = 22; > 72 END > 73 CASE(1) > 74 int type_[] = {1, 1}; > 75 vector <int> type(type_, type_+sizeof(type_)/sizeof(*type_)); > 76 int taste_[] = {-1, -1}; > 77 vector <int> taste(taste_, taste_+sizeof(taste_)/sizeof(*taste_)); > 78 int _ = 0; > 79 END > 80 CASE(2) > 81 int type_[] = {1, 2, 3}; > 82 vector <int> type(type_, type_+sizeof(type_)/sizeof(*type_)); > 83 int taste_[] = {7, 4, -1}; > 84 vector <int> taste(taste_, taste_+sizeof(taste_)/sizeof(*taste_)); > 85 int _ = 30; > 86 END > 87 CASE(3) > 88 int type_[] = {1, 2, 3, 2, 3, 1, 3, 2, 3, 1, 1, 1}; > 89 vector <int> type(type_, type_+sizeof(type_)/sizeof(*type_)); > 90 int taste_[] = {1, 7, -2, 3, -4, -1, 3, 1, 3, -5, -1, 0}; > 91 vector <int> taste(taste_, taste_+sizeof(taste_)/sizeof(*taste_)); > 92 int _ = 54; > 93 END > 94 CASE(4) > 95 int type_[] = {30, 20, 10}; > 96 vector <int> type(type_, type_+sizeof(type_)/sizeof(*type_)); > 97 int taste_[] = {100000, -100000, 100000}; > 98 vector <int> taste(taste_, taste_+sizeof(taste_)/sizeof(*taste_)); > 99 int _ = 400000; > 100 END > 101 CASE(5) > 102 int type_[] = {1,2,4,4,3}; > 103 vector <int> type(type_, type_+sizeof(type_)/sizeof(*type_)); > 104 int taste_[] = {100,100,-1,-1,-1}; > 105 vector <int> taste(taste_, taste_+sizeof(taste_)/sizeof(*taste_)); > 106 int _ = 792; > 107 END > 108 /* > 109 CASE(6) > 110 int type_[] = ; > 111 vector <int> type(type_, type_+sizeof(type_)/sizeof(*type_)); > 112 int taste_[] = ; > 113 vector <int> taste(taste_, taste_+sizeof(taste_)/sizeof(*taste_)); > 114 int _ = ; > 115 END > 116 */ > 117 } > 118 // END CUT HERE
Added SRM/605-U/1B.cpp version [ae835c90175ffde0]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 using namespace std; > 6 > 7 static const unsigned MODVAL = 1000000007; > 8 struct mint > 9 { > 10 unsigned val; > 11 mint():val(0){} > 12 mint(int x):val(x%MODVAL) {} > 13 mint(unsigned x):val(x%MODVAL) {} > 14 }; > 15 mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } > 16 > 17 class AlienAndSetDiv1 { public: > 18 int getNumber(int N, int K) > 19 { > 20 memo.assign((1<<K)*(N+1)*(N+1), -1); > 21 vector<int> A, B; > 22 return rec(N, K, A, B, 0); > 23 } > 24 > 25 vector<int> memo; > 26 int rec(size_t N, int K, vector<int>& A, vector<int>& B, int lastk) > 27 { > 28 if(A.size()==N && B.size()==N) > 29 return 1; > 30 > 31 auto key = (lastk*(N+1)+A.size())*(N+1)+B.size(); > 32 if(memo[key] >= 0) > 33 return memo[key]; > 34 > 35 int next = A.size()+B.size()+1, nextmask = (lastk &~ (1<<(K-1))) > 36 int ai = A.size(), bi = B.size(); > 37 > 38 mint total = 0; > 39 > 40 A.push_back(next); > 41 if(A.size()<=N && (ai>=B.size() || abs(A[ai]-B[ai])>=K)) > 42 total += rec(N, K, A, B, nextmask); > 43 A.pop_back(); > 44 B.push_back(next); > 45 if(B.size()<=N && (bi>=A.size() || abs(A[bi]-B[bi])>=K)) > 46 total += rec(N, K, A, B, nextmask|1); > 47 B.pop_back(); > 48 > 49 return memo[key] = total.val; > 50 } > 51 }; > 52 > 53 // BEGIN CUT HERE > 54 #include <ctime> > 55 double start_time; string timer() > 56 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 57 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 58 { os << "{ "; > 59 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 60 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 61 void verify_case(const int& Expected, const int& Received) { > 62 bool ok = (Expected == Received); > 63 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 64 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 65 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 66 #define END verify_case(_, AlienAndSetDiv1().getNumber(N, K));} > 67 int main(){ > 68 > 69 CASE(0) > 70 int N = 2; > 71 int K = 2; > 72 int _ = 2; > 73 END > 74 CASE(1) > 75 int N = 3; > 76 int K = 1; > 77 int _ = 20; > 78 END > 79 CASE(2) > 80 int N = 4; > 81 int K = 2; > 82 int _ = 14; > 83 END > 84 CASE(3) > 85 int N = 10; > 86 int K = 7; > 87 int _ = 40; > 88 END > 89 CASE(4) > 90 int N = 50; > 91 int K = 10; > 92 int _ = -1; > 93 END > 94 CASE(5) > 95 int N = 50; > 96 int K = 1; > 97 int _ = -1; > 98 END > 99 CASE(5) > 100 int N = 50; > 101 int K = 2; > 102 int _ = -1; > 103 END > 104 CASE(5) > 105 int N = 50; > 106 int K = 4; > 107 int _ = -1; > 108 END > 109 CASE(5) > 110 int N = 2; > 111 int K = 2; > 112 int _ = 2; > 113 END > 114 } > 115 // END CUT HERE