Overview
| SHA1 Hash: | 490a8ed9243b2aaebce1593d09a0111c4b7d6b0b |
|---|---|
| Date: | 2011-05-17 14:56:31 |
| User: | kinaba |
| Comment: | 505 |
| 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/505-u/1Au.cpp version [9979db28a5ab5334]
> 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 RectangleArea { public: > 23 int minimumQueries(vector <string> known) > 24 { > 25 const int H = known.size(); > 26 const int W = known[0].size(); > 27 for(int y=0; y<H; ++y) > 28 for(int x=0; x<W; ++x) > 29 for(int Y=0; Y<H; ++Y) > 30 for(int X=0; X<W; ++X) > 31 if( make_pair(y,x) < make_pair(Y,X) && y!=Y && x!=X ) > 32 if( known[y][x]=='Y' && known[Y][X]=='Y' ) > 33 { > 34 if( known[y][X]=='Y' ) > 35 known[Y][x] = 'Y'; > 36 if( known[Y][x]=='Y' ) > 37 known[y][X] = 'Y'; > 38 } > 39 > 40 int tt = 0; > 41 for(int i=0; i<W; ++i) > 42 if( known[0][i]=='N' ) > 43 ++tt; > 44 int yy = 0; > 45 for(int i=0; i<H; ++i) > 46 if( known[i][0]=='N' ) > 47 ++yy; > 48 if( tt == 0 ) > 49 return yy; > 50 if( yy == 0 ) > 51 return tt; > 52 return -1; > 53 } > 54 }; > 55 > 56 // BEGIN CUT HERE > 57 #include <ctime> > 58 double start_time; string timer() > 59 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 60 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 61 { os << "{ "; > 62 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 63 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 64 void verify_case(const int& Expected, const int& Received) { > 65 bool ok = (Expected == Received); > 66 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 67 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 68 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 69 #define END verify_case(_, RectangleArea().minimumQueries(known));} > 70 int main(){ > 71 > 72 CASE(0) > 73 string known_[] = {"NN", > 74 "NN"}; > 75 vector <string> known(known_, known_+sizeof(known_)/sizeof(*known_)); > 76 int _ = 3; > 77 END > 78 CASE(1) > 79 string known_[] = {"YNY", > 80 "NYN", > 81 "YNY"}; > 82 vector <string> known(known_, known_+sizeof(known_)/sizeof(*known_)); > 83 int _ = 1; > 84 END > 85 CASE(2) > 86 string known_[] = {"YY", > 87 "YY", > 88 "YY", > 89 "YY"}; > 90 vector <string> known(known_, known_+sizeof(known_)/sizeof(*known_)); > 91 int _ = 0; > 92 END > 93 CASE(3) > 94 string known_[] = {"NNNNNNNNNN"}; > 95 vector <string> known(known_, known_+sizeof(known_)/sizeof(*known_)); > 96 int _ = 10; > 97 END > 98 CASE(4) > 99 string known_[] = {"NNYYYNN", > 100 "NNNNNYN", > 101 "YYNNNNY", > 102 "NNNYNNN", > 103 "YYNNNNY"}; > 104 vector <string> known(known_, known_+sizeof(known_)/sizeof(*known_)); > 105 int _ = 2; > 106 END > 107 CASE(5) > 108 string known_[] = { > 109 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 110 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 111 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 112 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 113 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 114 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 115 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 116 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 117 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 118 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 119 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 120 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 121 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 122 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 123 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 124 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 125 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 126 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 127 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 128 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 129 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 130 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 131 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 132 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 133 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 134 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 135 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 136 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 137 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 138 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 139 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 140 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 141 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 142 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 143 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 144 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 145 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 146 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 147 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 148 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 149 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 150 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 151 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 152 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 153 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 154 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 155 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 156 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 157 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 158 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 159 }; > 160 vector <string> known(known_, known_+sizeof(known_)/sizeof(*known_)); > 161 int _ = -1; > 162 END > 163 CASE(6) > 164 string known_[] = {"N"}; > 165 vector <string> known(known_, known_+sizeof(known_)/sizeof(*known_)); > 166 int _ = 1; > 167 END > 168 > 169 } > 170 // END CUT HERE
Added SRM/505-u/1B.cpp version [dc8b7855f7fb41f0]
> 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 SetMultiples { public: > 23 long long smallestSubset(long long A, long long B, long long C, long lon > 24 { > 25 vector< pair<LL,LL> > noneed( 1, make_pair(1,100000) ); > 26 > 27 LL cnt = 0; > 28 for(LL p=1; p<=100000; ++p) > 29 { > 30 if( A<=p&&p<=B || C<=p&&p<=D ) > 31 if( need(p, A, B, C, D) ) > 32 ++cnt; > 33 if( p > 1 ) { > 34 add(noneed, p, A, B); > 35 add(noneed, p, C, D); > 36 } > 37 } > 38 sort(noneed.begin(), noneed.end(), &my_order); > 39 LL a = count_need(noneed, A, B); > 40 LL b = count_need(noneed, C, D); > 41 return cnt + a + b; > 42 } > 43 > 44 static bool need(LL p, LL A, LL B, LL C, LL D) > 45 { > 46 return !covered(p,A,B) && !covered(p,C,D); > 47 } > 48 > 49 static bool covered(LL p, LL A, LL B) > 50 { > 51 LL lo = A%p==0 ? A/p : A/p+1; > 52 LL hi = B/p; > 53 return ( lo<=hi && 2<=hi ); > 54 } > 55 > 56 static void add(vector< pair<LL,LL> >& noneed, LL p, LL A, LL B) > 57 { > 58 LL lo = A%p==0 ? A/p : A/p+1; > 59 LL hi = B/p; > 60 if( lo <= hi ) > 61 noneed.push_back( make_pair(lo,hi) ); > 62 } > 63 > 64 static bool my_order( const pair<LL,LL>& lhs, const pair<LL,LL>& rhs ) > 65 { > 66 if( lhs.second != rhs.second ) > 67 return lhs.second > rhs.second; > 68 return lhs.first < rhs.first; > 69 } > 70 > 71 static LL count_need(const vector< pair<LL,LL> >& noneed, LL A, LL B) > 72 { > 73 LL cnt = 0; > 74 LL highest_need = B; > 75 for(int i=0; i<noneed.size(); ++i) > 76 { > 77 LL lo = noneed[i].first; > 78 LL hi = noneed[i].second; > 79 if( hi < highest_need ) > 80 cnt += max(0LL, highest_need - max(hi,A-1)); > 81 highest_need = min(highest_need, lo-1); > 82 if( highest_need < A ) > 83 return cnt; > 84 } > 85 return cnt + (highest_need - A + 1); > 86 } > 87 }; > 88 > 89 // BEGIN CUT HERE > 90 #include <ctime> > 91 double start_time; string timer() > 92 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 93 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 94 { os << "{ "; > 95 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 96 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 97 void verify_case(const long long& Expected, const long long& Received) { > 98 bool ok = (Expected == Received); > 99 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 100 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 101 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 102 #define END verify_case(_, SetMultiples().smallestSubset(A, B, C, D));} > 103 int main(){ > 104 > 105 CASE(0) > 106 long long A = 1LL; > 107 long long B = 1LL; > 108 long long C = 2LL; > 109 long long D = 2LL; > 110 long long _ = 1LL; > 111 END > 112 CASE(1) > 113 long long A = 1LL; > 114 long long B = 2LL; > 115 long long C = 3LL; > 116 long long D = 4LL; > 117 long long _ = 2LL; > 118 END > 119 CASE(2) > 120 long long A = 2LL; > 121 long long B = 3LL; > 122 long long C = 5LL; > 123 long long D = 7LL; > 124 long long _ = 3LL; > 125 END > 126 CASE(3) > 127 long long A = 1LL; > 128 long long B = 10LL; > 129 long long C = 100LL; > 130 long long D = 1000LL; > 131 long long _ = 500LL; > 132 END > 133 CASE(4) > 134 long long A = 1000000000LL; > 135 long long B = 2000000000LL; > 136 long long C = 9000000000LL; > 137 long long D = 10000000000LL; > 138 long long _ = 1254365078LL; > 139 END > 140 CASE(5) > 141 long long A = 1LL; > 142 long long B = 1000000000LL; > 143 long long C = 2000000000LL; > 144 long long D = 10000000000LL; > 145 long long _ = -1LL; > 146 END > 147 CASE(6) > 148 long long A = 1LL; > 149 long long B = 2LL; > 150 long long C = 3LL; > 151 long long D = 5LL; > 152 long long _ = 3LL; > 153 END > 154 > 155 } > 156 // END CUT HERE