Overview
| SHA1 Hash: | ba35b3a9cf1201e875336ba54dc7417160616956 |
|---|---|
| Date: | 2011-06-25 15:38:24 |
| User: | kinaba |
| Comment: | 510 |
| 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/510-U/1A.cpp version [4b8ef53b93c8e743]
> 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 <cstring> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class TheAlmostLuckyNumbersDivOne { public: > 23 LL rec(LL n, int miss_atmost=1, LL prefix=0) > 24 { > 25 if( n<prefix || miss_atmost<0 ) > 26 return 0; > 27 LL cnt = (prefix==0?0:1); > 28 for(int i=(prefix==0?1:0); i<=9; ++i) > 29 cnt += rec(n, miss_atmost-(i==4||i==7?0:1), prefix*10+i) > 30 return cnt; > 31 } > 32 LL find(LL a, LL b) > 33 { > 34 return rec(b) - rec(a-1); > 35 LL cnt = 0; > 36 for(int len=1; len<=16; ++len) // 長さ len の > 37 for(int pat=0; pat<(1<<len); ++pat) // ビットパターンを全列挙 > 38 { > 39 // [0,1] -> [4,7] に変えれば lucky number の全生成 > 40 LL val = 0; > 41 for(int i=0; i<len; ++i) > 42 val = val*10 + (pat&(1<<i) ? 7 : 4); > 43 if( a<=val && val<=b ) > 44 ++cnt; > 45 > 46 // Almost Lucky Number は 1 箇所違う > 47 for(int m=0; m<len; ++m) if(pat&(1<<m)) // 7 を変えて > 48 for(int mTo=(m==0?1:0); mTo<=9; ++mTo) i > 49 { > 50 LL val = 0; > 51 for(int i=0; i<len; ++i) > 52 val = val*10 + (i==m ? m > 53 if( a<=val && val<=b ) > 54 ++cnt; > 55 } > 56 } > 57 return cnt; > 58 } > 59 }; > 60 > 61 // BEGIN CUT HERE > 62 #include <ctime> > 63 double start_time; string timer() > 64 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 65 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 66 { os << "{ "; > 67 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 68 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 69 void verify_case(const long long& Expected, const long long& Received) { > 70 bool ok = (Expected == Received); > 71 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 72 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 73 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 74 #define END verify_case(_, TheAlmostLuckyNumbersDivOne().find(a, b));} > 75 int main(){ > 76 > 77 CASE(0) > 78 long long a = 4LL; > 79 long long b = 7LL; > 80 long long _ = 4LL; > 81 END > 82 CASE(1) > 83 long long a = 8LL; > 84 long long b = 19LL; > 85 long long _ = 4LL; > 86 END > 87 CASE(2) > 88 long long a = 28LL; > 89 long long b = 33LL; > 90 long long _ = 0LL; > 91 END > 92 CASE(3) > 93 long long a = 12345678900LL; > 94 long long b = 98765432100LL; > 95 long long _ = 91136LL; > 96 END > 97 CASE(4) > 98 long long a = 1LL; > 99 long long b = 10000000000000000LL; > 100 long long _ = -1LL; > 101 END > 102 CASE(5) > 103 long long a = 1LL; > 104 long long b = 1LL; > 105 long long _ = 1LL; > 106 END > 107 CASE(6) > 108 long long a = 1LL; > 109 long long b = 99LL; > 110 long long _ = -1LL; > 111 END > 112 > 113 } > 114 // END CUT HERE
Added SRM/510-U/1B-U.cpp version [29ee29a34dc5af35]
> 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 <cstring> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class TheLuckyGameDivOne { public: > 23 vector<LL> all; > 24 void computeAll() > 25 { > 26 for(int len=1; len<=11; ++len) > 27 { > 28 for(int pat=0; pat<(1<<len); ++pat) > 29 { > 30 LL val = 0; > 31 for(int i=0; i<len; ++i) > 32 val = val*10 + ((pat&(1<<i)) ? 7 : 4); > 33 all.push_back(val); > 34 } > 35 } > 36 sort(all.begin(), all.end()); > 37 } > 38 > 39 int find(long long a, long long b, long long jLen, long long bLen) > 40 { > 41 computeAll(); > 42 > 43 pair<LL,LL> rng(a, a+bLen-1); > 44 vector< pair<pair<LL,LL>,int> > pt; > 45 pt.push_back(make_pair(rng, count_of(rng))); > 46 if( rng.second+1 <= b ) { > 47 pair<LL,LL> rngP1(rng.first+1,rng.second+1); > 48 pt.push_back(make_pair(rngP1, count_of(rngP1))); > 49 } > 50 for(;;) { > 51 rng = go_next(rng); > 52 if( rng.second > b ) > 53 break; > 54 pair<LL,LL> rngM1(rng.first-1,rng.second-1); > 55 pt.push_back(make_pair(rngM1, count_of(rngM1))); > 56 pt.push_back(make_pair(rng, count_of(rng))); > 57 if( rng.second+1 <= b ) { > 58 pair<LL,LL> rngP1(rng.first+1,rng.second+1); > 59 pt.push_back(make_pair(rngP1, count_of(rngP1))); > 60 } > 61 } > 62 sort(pt.begin(), pt.end()); > 63 pt.erase(unique(pt.begin(), pt.end()), pt.end()); > 64 > 65 const LL xLen = jLen - bLen + 1; > 66 int theMax = 0; > 67 for(size_t i=0; i<pt.size(); ++i) > 68 { > 69 int theMin = 0x7fffffff; > 70 for(size_t j=i; j<pt.size() && pt[j].first.first<pt[i].f > 71 theMin = min(theMin, pt[j].second); > 72 theMax = max(theMax, theMin); > 73 } > 74 return theMax; > 75 } > 76 > 77 pair<LL,LL> go_next(pair<LL,LL> rng) > 78 { > 79 LL a = go_next(rng.first); > 80 LL b = go_next(rng.second); > 81 LL dif = min(a-rng.first, b-rng.second); > 82 return make_pair(rng.first+dif, rng.second+dif); > 83 } > 84 > 85 LL go_next(LL x) > 86 { > 87 return *upper_bound(all.begin(), all.end(), x); > 88 } > 89 > 90 int count_of(pair<LL,LL> rng) > 91 { > 92 LL a = rng.first; > 93 LL b = rng.second; > 94 vector<LL>::iterator s = lower_bound(all.begin(), all.end(), a); > 95 vector<LL>::iterator e = upper_bound(all.begin(), all.end(), b); > 96 return e-s; > 97 } > 98 }; > 99 > 100 // BEGIN CUT HERE > 101 #include <ctime> > 102 double start_time; string timer() > 103 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 104 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 105 { os << "{ "; > 106 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 107 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 108 void verify_case(const int& Expected, const int& Received) { > 109 bool ok = (Expected == Received); > 110 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 111 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 112 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 113 #define END verify_case(_, TheLuckyGameDivOne().find(a, b, jLen, bLen));} > 114 int main(){ > 115 > 116 CASE(0) > 117 long long a = 1LL; > 118 long long b = 10LL; > 119 long long jLen = 2LL; > 120 long long bLen = 1LL; > 121 int _ = 0; > 122 END > 123 CASE(1) > 124 long long a = 1LL; > 125 long long b = 100LL; > 126 long long jLen = 100LL; > 127 long long bLen = 100LL; > 128 int _ = 6; > 129 END > 130 CASE(2) > 131 long long a = 4LL; > 132 long long b = 8LL; > 133 long long jLen = 3LL; > 134 long long bLen = 2LL; > 135 int _ = 1; > 136 END > 137 CASE(3) > 138 long long a = 1LL; > 139 long long b = 100LL; > 140 long long jLen = 75LL; > 141 long long bLen = 50LL; > 142 int _ = 2; > 143 END > 144 CASE(4) > 145 long long a = 1LL; > 146 long long b = 1LL; > 147 long long jLen = 1LL; > 148 long long bLen = 1LL; > 149 int _ = 0; > 150 END > 151 CASE(5) > 152 long long a = 10000000000LL; > 153 long long b = 10000000000LL; > 154 long long jLen = 5000000000LL; > 155 long long bLen = 2000000000LL; > 156 int _ = -1; > 157 END > 158 > 159 } > 160 // END CUT HERE
Added SRM/510-U/1C-U.cpp version [7df1c0211e8d6875]
> 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 <cstring> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class TheLuckyBasesDivOne { public: > 23 set<LL> all; > 24 void computeAll() > 25 { > 26 for(int len=1; len<=15; ++len) > 27 { > 28 for(int pat=0; pat<(1<<len); ++pat) > 29 { > 30 LL val = 0; > 31 for(int i=0; i<len; ++i) > 32 val = val*10 + ((pat&(1<<i)) ? 7 : 4); > 33 all.insert(val); > 34 } > 35 } > 36 } > 37 > 38 long long find(long long n) > 39 { > 40 computeAll(); > 41 if( all.count(n) ) // if itself is lucky, then inf. > 42 return -1; > 43 > 44 LL cnt = 0; > 45 // 3 or more B-its > 46 for(LL B=2; B*B*B<=n; ++B) > 47 if( isLuckyBase(n, B) ) > 48 ++cnt; > 49 // 2 B-its > 50 for(set<LL>::iterator it=all.begin(); it!=all.end(); ++it) > 51 { > 52 LL r = n-*it; > 53 for(LL B=*it+1; B<=n/B && B*B<n; ++B) { > 54 if( r%B==0 && n/B<B && all.count(n/B) ) > 55 ++cnt; > 56 } > 57 } > 58 return cnt; > 59 } > 60 > 61 bool isLuckyBase(LL n, LL B) > 62 { > 63 for(;n; n/=B) > 64 if( !all.count(n%B) ) > 65 return false; > 66 return true; > 67 } > 68 }; > 69 > 70 // BEGIN CUT HERE > 71 #include <ctime> > 72 double start_time; string timer() > 73 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 74 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 75 { os << "{ "; > 76 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 77 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 78 void verify_case(const long long& Expected, const long long& Received) { > 79 bool ok = (Expected == Received); > 80 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 81 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 82 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 83 #define END verify_case(_, TheLuckyBasesDivOne().find(n));} > 84 int main(){ > 85 > 86 CASE(0) > 87 long long n = 255LL; > 88 long long _ = 2LL; > 89 END > 90 CASE(1) > 91 long long n = 474LL; > 92 long long _ = -1LL; > 93 END > 94 CASE(2) > 95 long long n = 13LL; > 96 long long _ = 0LL; > 97 END > 98 CASE(3) > 99 long long n = 4748LL; > 100 long long _ = 5LL; > 101 END > 102 CASE(4) > 103 long long n = 1LL; > 104 long long _ = 0LL; > 105 END > 106 CASE(5) > 107 long long n = 10000000000000000LL; > 108 long long _ = -1LL; > 109 END > 110 > 111 } > 112 // END CUT HERE
Added SRM/TCO11-1/A.cpp version [3a5fb18ce90cdda6]
> 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 <cstring> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class TripleStrings { public: > 23 int getMinimumOperations(string init, string goal) > 24 { > 25 for(int i=0; i<=init.size(); ++i) > 26 if( init.substr(i, init.size()-i) == goal.substr(0, init > 27 return 2*i; > 28 assert(false); > 29 return -1; > 30 } > 31 }; > 32 > 33 // BEGIN CUT HERE > 34 #include <ctime> > 35 double start_time; string timer() > 36 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 37 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 38 { os << "{ "; > 39 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 40 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 41 void verify_case(const int& Expected, const int& Received) { > 42 bool ok = (Expected == Received); > 43 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 44 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 45 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 46 #define END verify_case(_, TripleStrings().getMinimumOperations(init, goal) > 47 int main(){ > 48 > 49 CASE(0) > 50 string init = "ooxxox"; > 51 string goal = "xoxoxo"; > 52 int _ = 6; > 53 END > 54 CASE(1) > 55 string init = "oooxxoo"; > 56 string goal = "oooxxoo"; > 57 int _ = 0; > 58 END > 59 CASE(2) > 60 string init = "ox"; > 61 string goal = "xo"; > 62 int _ = 2; > 63 END > 64 CASE(3) > 65 string init = "ooxxooxx"; > 66 string goal = "xxoxoxoo"; > 67 int _ = 12; > 68 END > 69 CASE(4) > 70 string init = "oxxoxxoooxooooxxxoo"; > 71 string goal = "oxooooxxxooooxoxxxo"; > 72 int _ = 16; > 73 END > 74 CASE(5) > 75 string init = "xxxoxoxxooxooxoxooo"; > 76 string goal = "oxxooxxooxxoxoxooxo"; > 77 int _ = 36; > 78 END > 79 CASE(6) > 80 string init = "oxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxox"; > 81 string goal = "oooooooooooooooooooooooooxxxxxxxxxxxxxxxxxxxxxxxxx"; > 82 int _ = -1; > 83 END > 84 CASE(7) > 85 string init = "o"; > 86 string goal = "o"; > 87 int _ = 0; > 88 END > 89 CASE(8) > 90 string init = "ox"; > 91 string goal = "xo"; > 92 int _ = 2; > 93 END > 94 > 95 } > 96 // END CUT HERE
Added SRM/TCO11-1/B.cpp version [f52c1a0b3c125396]
> 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 <cstring> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class MuddyRoad { public: > 23 double getExpectedValue(vector <int> road) > 24 { > 25 double dp[50][2]; > 26 for(size_t g=0; g<road.size(); ++g) > 27 for(int leftmud=0; leftmud<2; ++leftmud) > 28 if( g >= 2 ) > 29 { > 30 const double p = road[g-2] / 100.0; > 31 const double q = (leftmud==1 ? 1.0 : roa > 32 double e = 0; > 33 e += (1-p) * (1-q) * dp[g-2][0]; > 34 e += (1-p) * q * dp[g-2][0]; > 35 e += p * (1-q) * dp[g-1][1]; > 36 e += p * q * (1 + dp[g-2][0]); > 37 dp[g][leftmud] = e; > 38 } > 39 else if( g == 1 ) > 40 { > 41 dp[g][leftmud] = 0; > 42 } > 43 else > 44 { > 45 dp[g][leftmud] = 0; > 46 } > 47 return dp[road.size()-1][0]; > 48 } > 49 }; > 50 > 51 // BEGIN CUT HERE > 52 #include <ctime> > 53 double start_time; string timer() > 54 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 55 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 56 { os << "{ "; > 57 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 58 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 59 void verify_case(const double& Expected, const double& Received) { > 60 bool ok = (abs(Expected - Received) < 1e-9); > 61 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 62 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 63 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 64 #define END verify_case(_, MuddyRoad().getExpectedValue(road));} > 65 int main(){ > 66 > 67 CASE(0) > 68 int road_[] = {0, 60, 60, 0}; > 69 vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_)); > 70 double _ = 0.36; > 71 END > 72 CASE(1) > 73 int road_[] = {0, 50, 50, 50, 50, 0}; > 74 vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_)); > 75 double _ = 0.5625; > 76 END > 77 CASE(2) > 78 int road_[] = {0, 0, 100, 100, 100, 100, 100, 100, 0, 0, 100, 0}; > 79 vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_)); > 80 double _ = 3.0; > 81 END > 82 CASE(3) > 83 int road_[] = {0, 12, 34, 56, 78, 91, 23, 45, 67, 89, 0}; > 84 vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_)); > 85 double _ = 1.7352539420031923; > 86 END > 87 CASE(4) > 88 int road_[] = {0, 50, 50, 100, 50, 100, 50, 50, 100, 66, 0}; > 89 vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_)); > 90 double _ = 2.288125; > 91 END > 92 CASE(5) > 93 int road_[] = {0,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50, > 94 vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_)); > 95 double _ = 1.0; > 96 END > 97 CASE(6) > 98 int road_[] = {0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 > 99 vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_)); > 100 double _ = -1; > 101 END > 102 > 103 } > 104 // END CUT HERE
Added SRM/TCO11-1/C.cpp version [7383f594e5758776]
> 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 <cstring> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class IPv444 { public: > 23 struct Request > 24 { > 25 int x[4]; > 26 int y[4]; > 27 LL p; > 28 Request(const string& r, LL p) : p(p) > 29 { > 30 for(int d=0,s=0; d<4; ++d) > 31 { > 32 int e=s+1; > 33 while( e<r.size() && r[e]!='.' ) > 34 ++e; > 35 string num(r.begin()+s, r.begin()+e); > 36 if( num == "*" ) { > 37 x[d] = 0; > 38 y[d] = 1000; > 39 } > 40 else { > 41 x[d] = atoi(num.c_str()); > 42 y[d] = x[d]+1; > 43 } > 44 s = e+1; > 45 } > 46 } > 47 > 48 bool operator<(const Request& rhs) const > 49 { > 50 if( p != rhs.p ) > 51 return p < rhs.p; > 52 for(int d=0; d<4; ++d) > 53 if( x[d] != rhs.x[d] ) > 54 return x[d] < rhs.x[d]; > 55 return false; > 56 } > 57 }; > 58 > 59 long long getMaximumMoney(vector <string> request, vector <int> price) > 60 { > 61 vector<Request> req; > 62 for(size_t i=0; i<request.size(); ++i) > 63 req.push_back( Request(request[i], price[i]) ); > 64 sort(req.rbegin(), req.rend()); > 65 > 66 static const int MID = 2; > 67 > 68 vector<int> sig[4]; > 69 for(int d=0; d<MID; ++d) > 70 { > 71 set<int> sigs; > 72 for(int i=0; i<req.size(); ++i) > 73 { > 74 sigs.insert(req[i].x[d]); > 75 sigs.insert(req[i].y[d]); > 76 } > 77 sig[d].assign(sigs.begin(), sigs.end()); > 78 } > 79 > 80 LL sum = 0; > 81 int i[4]; > 82 for(i[0]=0; i[0]+1<sig[0].size(); ++i[0]) > 83 for(i[1]=0; i[1]+1<sig[1].size(); ++i[1]) > 84 { > 85 for(int d=MID; d<4; ++d) > 86 { > 87 set<int> sigs; > 88 for(int k=0; k<req.size(); ++k) > 89 { > 90 bool dame = false; > 91 for(int dd=0; dd<MID; ++dd) > 92 if( !(req[k].x[dd]<=sig[dd][i[dd > 93 dame = true; > 94 if(!dame) > 95 { > 96 sigs.insert(req[k].x[d]); > 97 sigs.insert(req[k].y[d]); > 98 } > 99 } > 100 sig[d].assign(sigs.begin(), sigs.end()); > 101 } > 102 for(i[2]=0; i[2]+1<sig[2].size(); ++i[2]) > 103 for(i[3]=0; i[3]+1<sig[3].size(); ++i[3]) > 104 { > 105 LL p = 0; > 106 for(int k=0; k<req.size(); ++k) > 107 { > 108 bool dame = false; > 109 for(int d=0; d<4; ++d) > 110 if( !(req[k].x[d]<=sig[d][i[d]] > 111 dame = true; > 112 if(!dame) > 113 {p = req[k].p; break;} > 114 } > 115 LL a = p; > 116 for(int dd=0; dd<4; ++dd) > 117 a *= sig[dd][i[dd]+1] - sig[dd][i[dd]]; > 118 sum += a; > 119 } > 120 } > 121 return sum; > 122 } > 123 }; > 124 > 125 // BEGIN CUT HERE > 126 #include <ctime> > 127 double start_time; string timer() > 128 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 129 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 130 { os << "{ "; > 131 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 132 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 133 void verify_case(const long long& Expected, const long long& Received) { > 134 bool ok = (Expected == Received); > 135 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 136 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 137 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 138 #define END verify_case(_, IPv444().getMaximumMoney(request, price));} > 139 int main(){ > 140 > 141 CASE(0) > 142 string request_[] = {"66.37.210.86"}; > 143 vector <string> request(request_, request_+sizeof(request_)/sizeof(*re > 144 int price_[] = {47}; > 145 vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); > 146 long long _ = 47LL; > 147 END > 148 CASE(1) > 149 string request_[] = {"0.0.0.*", "0.0.0.3", "0.0.0.5"}; > 150 vector <string> request(request_, request_+sizeof(request_)/sizeof(*re > 151 int price_[] = {1, 3, 9}; > 152 vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); > 153 long long _ = 1010LL; > 154 END > 155 CASE(2) > 156 string request_[] = {"*.*.*.*", "123.456.789.0", "434.434.434.434", "999 > 157 vector <string> request(request_, request_+sizeof(request_)/sizeof(*re > 158 int price_[] = {1, 5, 3, 6}; > 159 vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); > 160 long long _ = 1000005000006LL; > 161 END > 162 CASE(3) > 163 string request_[] = {"*.*.999.999", "888.888.999.*", "888.888.*.999", "7 > 164 vector <string> request(request_, request_+sizeof(request_)/sizeof(*re > 165 int price_[] = {19, 33, 42, 777, 7}; > 166 vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); > 167 long long _ = 26075718LL; > 168 END > 169 CASE(4) > 170 string request_[] = {"127.0.0.1", "*.0.0.*", "*.*.255.255", "192.68.*.*" > 171 vector <string> request(request_, request_+sizeof(request_)/sizeof(*re > 172 int price_[] = {999999, 629851, 294016, 438090}; > 173 vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); > 174 long long _ = 1361957076132LL; > 175 END > 176 CASE(5) > 177 string request_[] = { > 178 "1.1.1.1", > 179 "3.3.3.3", > 180 "5.5.5.5", > 181 "7.7.7.7", > 182 "9.9.9.9", > 183 "11.11.11.11", > 184 "13.13.13.13", > 185 "15.15.15.15", > 186 "17.17.17.17", > 187 "19.19.19.19", > 188 "21.21.21.21", > 189 "23.23.23.23", > 190 "25.25.25.25", > 191 "27.27.27.27", > 192 "29.29.29.29", > 193 "31.31.31.31", > 194 "33.33.33.33", > 195 "35.35.35.35", > 196 "37.37.37.37", > 197 "39.39.39.39", > 198 "41.41.41.41", > 199 "43.43.43.43", > 200 "45.45.45.45", > 201 "47.47.47.47", > 202 "49.49.49.49", > 203 "51.51.51.51", > 204 "53.53.53.53", > 205 "55.55.55.55", > 206 "57.57.57.57", > 207 "59.59.59.59", > 208 }; > 209 vector <string> request(request_, request_+sizeof(request_)/sizeof(*re > 210 int price_[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, > 211 vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); > 212 long long _ = -1LL; > 213 END > 214 /* > 215 CASE(6) > 216 string request_[] = ; > 217 vector <string> request(request_, request_+sizeof(request_)/sizeof(*re > 218 int price_[] = ; > 219 vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); > 220 long long _ = LL; > 221 END > 222 */ > 223 } > 224 // END CUT HERE