Overview
| SHA1 Hash: | 74d1f45c5c2866c04c09441813737491abc66194 |
|---|---|
| Date: | 2014-10-14 10:36:47 |
| User: | kinaba |
| Comment: | 635 |
| 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/635-U/1A-U.cpp version [bca49fe15601fcf2]
> 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 SimilarRatingGraph { public: > 23 double maxLength(vector <int> date, vector <int> rating) > 24 { > 25 const int N = date.size(); > 26 double best = 0.0; > 27 > 28 for(int s=0; s+1<N; ++s) > 29 for(int t=s+1; t+1<N; ++t) > 30 { > 31 // a d[s] + b = d[t] > 32 // a d[s+1] + b = d[t+1] > 33 // a r[s] + c = r[t] > 34 // a r[s+1] + c = r[t+1] > 35 > 36 double a = (date[t+1]-date[t]) / double(date[s+1] - date > 37 double b = date[t] - a*date[s]; > 38 double c = rating[t] - a*rating[s]; > 39 > 40 double l1=0.0, l2=0.0; > 41 for(int k=1; t+k<N; ++k) { > 42 if( !eq(a*date[s+k]+b, date[t+k]) ) break; > 43 if( !eq(a*rating[s+k]+c, rating[t+k]) ) break; > 44 l1 += sqrt(pow(date[s+k]-date[s+k-1],2) + pow(ra > 45 l2 += sqrt(pow(date[t+k]-date[t+k-1],2) + pow(ra > 46 } > 47 best = max(best, max(l1, l2)); > 48 } > 49 return best; > 50 } > 51 > 52 double eq(double x, int v) { > 53 return int(floor(x+0.5)) == v; > 54 } > 55 }; > 56 > 57 // BEGIN CUT HERE > 58 #include <ctime> > 59 double start_time; string timer() > 60 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 61 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 62 { os << "{ "; > 63 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 64 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 65 void verify_case(const double& Expected, const double& Received) { > 66 bool ok = (abs(Expected - Received) < 1e-9); > 67 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 68 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 69 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 70 #define END verify_case(_, SimilarRatingGraph().maxLength(date, rating));} > 71 int main(){ > 72 > 73 CASE(0) > 74 int date_[] = {1,2,4,8,16,32}; > 75 vector <int> date(date_, date_+sizeof(date_)/sizeof(*date_)); > 76 int rating_[] = {1,2,4,8,16,32}; > 77 vector <int> rating(rating_, rating_+sizeof(rating_)/sizeof(*rating_)) > 78 double _ = 42.42640687119285; > 79 END > 80 CASE(1) > 81 int date_[] = {81,104,120,124,134,137}; > 82 vector <int> date(date_, date_+sizeof(date_)/sizeof(*date_)); > 83 int rating_[] = {1866,2332,2510,2678,2876,3002}; > 84 vector <int> rating(rating_, rating_+sizeof(rating_)/sizeof(*rating_)) > 85 double _ = 168.04761230080004; > 86 END > 87 CASE(2) > 88 int date_[] = {10,11,13,15,19}; > 89 vector <int> date(date_, date_+sizeof(date_)/sizeof(*date_)); > 90 int rating_[] = {10,14,15,23,25}; > 91 vector <int> rating(rating_, rating_+sizeof(rating_)/sizeof(*rating_)) > 92 double _ = 12.7183472062349; > 93 END > 94 CASE(3) > 95 int date_[] = {1,2,3,4}; > 96 vector <int> date(date_, date_+sizeof(date_)/sizeof(*date_)); > 97 int rating_[] = {1700,1800,1750,1850}; > 98 vector <int> rating(rating_, rating_+sizeof(rating_)/sizeof(*rating_)) > 99 double _ = 100.00499987500625; > 100 END > 101 CASE(4) > 102 int date_[] = {1,2,3,4}; > 103 vector <int> date(date_, date_+sizeof(date_)/sizeof(*date_)); > 104 int rating_[] = {1,4,9,16}; > 105 vector <int> rating(rating_, rating_+sizeof(rating_)/sizeof(*rating_)) > 106 double _ = 0.0; > 107 END > 108 CASE(5) > 109 int date_[] = {5,11,25,58,92,162,255,350,458,566,677,792,919,1051,1189,1 > 110 vector <int> date(date_, date_+sizeof(date_)/sizeof(*date_)); > 111 int rating_[] = {1505,1462,1436,1416,1463,1421,1411,1450,1497,1465,1423, > 112 vector <int> rating(rating_, rating_+sizeof(rating_)/sizeof(*rating_)) > 113 double _ = 11940.179271014536; > 114 END > 115 /* > 116 CASE(6) > 117 int date_[] = ; > 118 vector <int> date(date_, date_+sizeof(date_)/sizeof(*date_)); > 119 int rating_[] = ; > 120 vector <int> rating(rating_, rating_+sizeof(rating_)/sizeof(*rating_)) > 121 double _ = ; > 122 END > 123 CASE(7) > 124 int date_[] = ; > 125 vector <int> date(date_, date_+sizeof(date_)/sizeof(*date_)); > 126 int rating_[] = ; > 127 vector <int> rating(rating_, rating_+sizeof(rating_)/sizeof(*rating_)) > 128 double _ = ; > 129 END > 130 */ > 131 } > 132 // END CUT HERE
Added SRM/635-U/1B.cpp version [be8a1473abc3cb76]
> 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 StoryFromTCO { public: > 23 int minimumChanges(vector <int> places, vector <int> cutoff) > 24 { > 25 const int N = places.size(); > 26 vector<pair<int,int>> cp; > 27 for(int i=0; i<N; ++i) > 28 cp.emplace_back(cutoff[i], places[i]); > 29 sort(cp.begin(), cp.end()); > 30 > 31 vector<int> lm(N); // i-th place candidate can be put at >=lm[i > 32 for(int i=0; i<N; ++i) { > 33 int p=cp[i].second, k=0; > 34 for(; k<N; ++k) > 35 if(p <= cp[k].first) > 36 break; > 37 if(k == N) > 38 return -1; > 39 lm[i] = k; > 40 } > 41 return solve(lm); > 42 } > 43 > 44 // reorder v so that v[i]<=i for all i. > 45 int solve(vector<int> v) > 46 { > 47 const int N = v.size(); > 48 const int HOLE = 0x7fffffff; > 49 int ans = 0; > 50 multiset<int> stock; > 51 for(int i=0; i<N; ++i) > 52 if(!(v[i]<=i)) { > 53 if(stock.empty() || !(*stock.begin()<=i)) { > 54 // find right most fitting elem. > 55 for(int k=N-1; k>i; --k) > 56 if(v[k]<=i) { > 57 stock.insert(v[k]); > 58 v[k] = HOLE; > 59 break; > 60 } > 61 } > 62 > 63 if(stock.empty() || !(*stock.begin()<=i)) > 64 return -1; > 65 > 66 ++ans; > 67 if(v[i] != HOLE) stock.insert(v[i]); > 68 v[i] = *stock.begin(); > 69 stock.erase(stock.begin()); > 70 } > 71 return ans; > 72 } > 73 }; > 74 > 75 // BEGIN CUT HERE > 76 #include <ctime> > 77 double start_time; string timer() > 78 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 79 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 80 { os << "{ "; > 81 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 82 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 83 void verify_case(const int& Expected, const int& Received) { > 84 bool ok = (Expected == Received); > 85 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 86 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 87 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 88 #define END verify_case(_, StoryFromTCO().minimumChanges(places, cutoff));} > 89 int main(){ > 90 > 91 CASE(0) > 92 int places_[] = {20,100,500,50}; > 93 vector <int> places(places_, places_+sizeof(places_)/sizeof(*places_)) > 94 int cutoff_[] = {7500,2250,150,24}; > 95 vector <int> cutoff(cutoff_, cutoff_+sizeof(cutoff_)/sizeof(*cutoff_)) > 96 int _ = 3; > 97 END > 98 CASE(1) > 99 int places_[] = {5,4,3,2,1}; > 100 vector <int> places(places_, places_+sizeof(places_)/sizeof(*places_)) > 101 int cutoff_[] = {5,4,3,2,1}; > 102 vector <int> cutoff(cutoff_, cutoff_+sizeof(cutoff_)/sizeof(*cutoff_)) > 103 int _ = 0; > 104 END > 105 CASE(2) > 106 int places_[] = {1,5,5,5}; > 107 vector <int> places(places_, places_+sizeof(places_)/sizeof(*places_)) > 108 int cutoff_[] = {8,6,4,2}; > 109 vector <int> cutoff(cutoff_, cutoff_+sizeof(cutoff_)/sizeof(*cutoff_)) > 110 int _ = -1; > 111 END > 112 CASE(3) > 113 int places_[] = {3,1,5}; > 114 vector <int> places(places_, places_+sizeof(places_)/sizeof(*places_)) > 115 int cutoff_[] = {6,4,2}; > 116 vector <int> cutoff(cutoff_, cutoff_+sizeof(cutoff_)/sizeof(*cutoff_)) > 117 int _ = 3; > 118 END > 119 CASE(4) > 120 int places_[] = {14,11,42,9,19}; > 121 vector <int> places(places_, places_+sizeof(places_)/sizeof(*places_)) > 122 int cutoff_[] = {11,16,37,41,47} > 123 ; > 124 vector <int> cutoff(cutoff_, cutoff_+sizeof(cutoff_)/sizeof(*cutoff_)) > 125 int _ = 4; > 126 END > 127 CASE(5) > 128 int places_[] = {4,1,3,3,2,4,5,5,4,4}; > 129 vector <int> places(places_, places_+sizeof(places_)/sizeof(*places_)) > 130 int cutoff_[] = {3,3,5,2,4,4,5,4,3,5}; > 131 vector <int> cutoff(cutoff_, cutoff_+sizeof(cutoff_)/sizeof(*cutoff_)) > 132 int _ = 6; > 133 END > 134 CASE(6) > 135 int places_[] = {213,177,237,444,497,315,294,104,522,635,13,26,22,276,88 > 136 53,132,178,250,18,210,492,181,2,99,29,21,62,218,188,584,702,63,41,79,28,452,2}; > 137 vector <int> places(places_, places_+sizeof(places_)/sizeof(*places_)) > 138 int cutoff_[] = {33,40,41,48,74,84,117,125,126,164,197,197,201,218,222,2 > 139 442,465,477,491,513,639,645,647,675,706,710,726,736,736,765,801,838,845,854,863, > 140 vector <int> cutoff(cutoff_, cutoff_+sizeof(cutoff_)/sizeof(*cutoff_)) > 141 int _ = 23; > 142 END > 143 /* > 144 CASE(7) > 145 int places_[] = ; > 146 vector <int> places(places_, places_+sizeof(places_)/sizeof(*places_)) > 147 int cutoff_[] = ; > 148 vector <int> cutoff(cutoff_, cutoff_+sizeof(cutoff_)/sizeof(*cutoff_)) > 149 int _ = ; > 150 END > 151 CASE(8) > 152 int places_[] = ; > 153 vector <int> places(places_, places_+sizeof(places_)/sizeof(*places_)) > 154 int cutoff_[] = ; > 155 vector <int> cutoff(cutoff_, cutoff_+sizeof(cutoff_)/sizeof(*cutoff_)) > 156 int _ = ; > 157 END > 158 */ > 159 } > 160 // END CUT HERE
Added SRM/635-U/1C-U.cpp version [a30b933135e9f75c]
> 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 = 1000000009; > 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*=x; return 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 class ColourHolic { public: > 43 int countSequences(vector <int> n) > 44 { > 45 mint ans = 0; > 46 for(int c=0; c<4; ++c) if(n[c]) { > 47 n[c]--; > 48 ans += calc(c, n); > 49 n[c]++; > 50 } > 51 return ans.val; > 52 } > 53 > 54 map<LL, mint> memo; > 55 mint calc(int cp, vector<int>& n) > 56 { > 57 if(n[0]+n[1]+n[2]+n[3]==0) > 58 return 1; > 59 > 60 vector<int> nn; > 61 for(int c=0; c<4; ++c) if(c!=cp) > 62 nn.push_back(n[c]); > 63 sort(nn.begin(), nn.end()); > 64 LL key = n[cp]; > 65 for(int v: nn) > 66 key=key*50001+v; > 67 if(memo.count(key)) > 68 return memo[key]; > 69 > 70 int tot = accumulate(n.begin(), n.end(), 0); > 71 int ma = max(nn.front(), nn.back()); > 72 if(ma*2 > tot+1) > 73 return 0; > 74 > 75 mint ans = 0; > 76 for(int c=0; c<4; ++c) if(c!=cp && n[c]) { > 77 n[c]--; > 78 ans += calc(c, n); > 79 n[c]++; > 80 } > 81 return memo[key] = ans; > 82 } > 83 }; > 84 > 85 // BEGIN CUT HERE > 86 #include <ctime> > 87 double start_time; string timer() > 88 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 89 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 90 { os << "{ "; > 91 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 92 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 93 void verify_case(const int& Expected, const int& Received) { > 94 bool ok = (Expected == Received); > 95 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 96 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 97 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 98 #define END verify_case(_, ColourHolic().countSequences(n));} > 99 int main(){ > 100 > 101 CASE(0) > 102 int n_[] = {1,0,2,3}; > 103 vector <int> n(n_, n_+sizeof(n_)/sizeof(*n_)); > 104 int _ = 10; > 105 END > 106 CASE(1) > 107 int n_[] = {1,1,1,1}; > 108 vector <int> n(n_, n_+sizeof(n_)/sizeof(*n_)); > 109 int _ = 24; > 110 END > 111 CASE(2) > 112 int n_[] = {42,42,42,9001}; > 113 vector <int> n(n_, n_+sizeof(n_)/sizeof(*n_)); > 114 int _ = 0; > 115 END > 116 CASE(3) > 117 int n_[] = {8,0,0,8}; > 118 vector <int> n(n_, n_+sizeof(n_)/sizeof(*n_)); > 119 int _ = 2; > 120 END > 121 CASE(4) > 122 int n_[] = {0,5,1,3}; > 123 vector <int> n(n_, n_+sizeof(n_)/sizeof(*n_)); > 124 int _ = 4; > 125 END > 126 CASE(5) > 127 int n_[] = {4,2,1,3}; > 128 vector <int> n(n_, n_+sizeof(n_)/sizeof(*n_)); > 129 int _ = 1074; > 130 END > 131 CASE(6) > 132 int n_[] = {15,900,357,22}; > 133 vector <int> n(n_, n_+sizeof(n_)/sizeof(*n_)); > 134 int _ = 0; > 135 END > 136 CASE(7) > 137 int n_[] = {110,30000,200,29999}; > 138 vector <int> n(n_, n_+sizeof(n_)/sizeof(*n_)); > 139 int _ = 118115350; > 140 END > 141 /* > 142 CASE(8) > 143 int n_[] = ; > 144 vector <int> n(n_, n_+sizeof(n_)/sizeof(*n_)); > 145 int _ = ; > 146 END > 147 CASE(9) > 148 int n_[] = ; > 149 vector <int> n(n_, n_+sizeof(n_)/sizeof(*n_)); > 150 int _ = ; > 151 END > 152 */ > 153 } > 154 // END CUT HERE