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[s]); 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(rating[s+k]-rating[s+k-1],2)); 45 + l2 += sqrt(pow(date[t+k]-date[t+k-1],2) + pow(rating[t+k]-rating[t+k-1],2)); 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 68 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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,1331,1489,1673,1882,2093,2315,2541,2771,3012,3254,3524,3797,4087,4379,4675,4973,5278,5588,5904,6225,6550,6888,7249,7612,8018,8428,8847,9267,9688,10109,10530,10964,11407,11870,12340,12811,13288,13768,14249,14734,15242,15774,16306,16847,17400,17966,18533,19108,19692,20278,20871,21471,22074,22679,23297,23916,24553,25190,25829,26472,27135,27814,28497,29181,29865,30555,31272,31994,32729,33487,34246,35005,35764,36537,37326,38119,38913,39725,40538,41360,42185,43010,43840,44671,45509,46350,47205,48063,48932,49807,50691,51577,52464,53289,54119,54950,55788,56629,57484,58342,59211,60086,60970,61856,62743,63568,64398,65388}; 110 + vector <int> date(date_, date_+sizeof(date_)/sizeof(*date_)); 111 + int rating_[] = {1505,1462,1436,1416,1463,1421,1411,1450,1497,1465,1423,1394,1391,1367,1358,1323,1310,1279,1268,1279,1311,1342,1359,1387,1414,1376,1424,1382,1373,1335,1359,1318,1275,1266,1227,1203,1168,1163,1184,1144,1169,1207,1250,1235,1209,1162,1124,1148,1168,1202,1190,1155,1179,1194,1195,1195,1203,1240,1218,1245,1220,1190,1208,1180,1182,1148,1139,1126,1152,1159,1147,1158,1112,1091,1101,1116,1123,1086,1126,1110,1128,1085,1132,1145,1135,1140,1117,1081,1120,1131,1081,1032,1071,1102,1071,1065,1068,1027,980,947,987,968,959,980,990,974,1003,996,999,958,911,878,918,899,890,911,921,905,934,927,930,889,844}; 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 86 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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,249,374,17,42,245,80,553,121,625,62,105, 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,231,244,277,290,309,321,321,360,376,440, 139 +442,465,477,491,513,639,645,647,675,706,710,726,736,736,765,801,838,845,854,863,865,887,902,908}; 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 96 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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