Overview
| SHA1 Hash: | 2024b9fa5d0676cc468ee69ab03a43e6d5073530 |
|---|---|
| Date: | 2016-01-23 12:59:51 |
| User: | kinaba |
| Comment: | 679 |
| 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/679/1A.cpp version [8502d7bbdeef57a7]
> 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 FiringEmployees { public: > 23 int fire(vector <int> manager, vector <int> salary, vector <int> product > 24 { > 25 const int N = manager.size()+1; > 26 > 27 vector<vector<int>> children(N); > 28 for(int i=1; i<N; ++i) > 29 children[manager[i-1]].push_back(i); > 30 > 31 vector<int> best(N); > 32 for(int i=N-1; i>=0; --i) { > 33 int total = (i ? productivity[i-1] - salary[i-1] : 0); > 34 for(int u: children[i]) > 35 total += best[u]; > 36 if(total > 0) > 37 best[i] = total; > 38 } > 39 return best[0]; > 40 } > 41 }; > 42 > 43 // BEGIN CUT HERE > 44 #include <ctime> > 45 double start_time; string timer() > 46 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 47 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 48 { os << "{ "; > 49 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 50 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 51 void verify_case(const int& Expected, const int& Received) { > 52 bool ok = (Expected == Received); > 53 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 54 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 55 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 56 #define END verify_case(_, FiringEmployees().fire(manager, salary, producti > 57 int main(){ > 58 > 59 CASE(0) > 60 int manager_[] = {0,0,0}; > 61 vector <int> manager(manager_, manager_+sizeof(manager_)/sizeof(*manag > 62 int salary_[] = {1,2,3}; > 63 vector <int> salary(salary_, salary_+sizeof(salary_)/sizeof(*salary_)) > 64 int productivity_[] = {3,2,1}; > 65 vector <int> productivity(productivity_, productivity_+sizeof(producti > 66 int _ = 2; > 67 END > 68 CASE(1) > 69 int manager_[] = {0,1,2,3}; > 70 vector <int> manager(manager_, manager_+sizeof(manager_)/sizeof(*manag > 71 int salary_[] = {4,3,2,1}; > 72 vector <int> salary(salary_, salary_+sizeof(salary_)/sizeof(*salary_)) > 73 int productivity_[] = {2,3,4,5}; > 74 vector <int> productivity(productivity_, productivity_+sizeof(producti > 75 int _ = 4; > 76 END > 77 CASE(2) > 78 int manager_[] = {0,1}; > 79 vector <int> manager(manager_, manager_+sizeof(manager_)/sizeof(*manag > 80 int salary_[] = {1,10}; > 81 vector <int> salary(salary_, salary_+sizeof(salary_)/sizeof(*salary_)) > 82 int productivity_[] = {5,5}; > 83 vector <int> productivity(productivity_, productivity_+sizeof(producti > 84 int _ = 4; > 85 END > 86 CASE(3) > 87 int manager_[] = {0,1,2,1,2,3,4,2,3}; > 88 vector <int> manager(manager_, manager_+sizeof(manager_)/sizeof(*manag > 89 int salary_[] = {5,3,6,8,4,2,4,6,7}; > 90 vector <int> salary(salary_, salary_+sizeof(salary_)/sizeof(*salary_)) > 91 int productivity_[] = {2,5,7,8,5,3,5,7,9}; > 92 vector <int> productivity(productivity_, productivity_+sizeof(producti > 93 int _ = 6; > 94 END > 95 CASE(4) > 96 int manager_[] = {0,0,1,1,2,2}; > 97 vector <int> manager(manager_, manager_+sizeof(manager_)/sizeof(*manag > 98 int salary_[] = {1,1,1,2,2,2}; > 99 vector <int> salary(salary_, salary_+sizeof(salary_)/sizeof(*salary_)) > 100 int productivity_[] = {2,2,2,1,1,1}; > 101 vector <int> productivity(productivity_, productivity_+sizeof(producti > 102 int _ = 3; > 103 END > 104 /* > 105 CASE(5) > 106 int manager_[] = ; > 107 vector <int> manager(manager_, manager_+sizeof(manager_)/sizeof(*manag > 108 int salary_[] = ; > 109 vector <int> salary(salary_, salary_+sizeof(salary_)/sizeof(*salary_)) > 110 int productivity_[] = ; > 111 vector <int> productivity(productivity_, productivity_+sizeof(producti > 112 int _ = ; > 113 END > 114 CASE(6) > 115 int manager_[] = ; > 116 vector <int> manager(manager_, manager_+sizeof(manager_)/sizeof(*manag > 117 int salary_[] = ; > 118 vector <int> salary(salary_, salary_+sizeof(salary_)/sizeof(*salary_)) > 119 int productivity_[] = ; > 120 vector <int> productivity(productivity_, productivity_+sizeof(producti > 121 int _ = ; > 122 END > 123 */ > 124 } > 125 // END CUT HERE
Added SRM/679/1B.cpp version [88a9946483caf8ed]
> 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 double outer_prod(const CMP& a, const CMP& b) { return imag(conj(a)*b); } > 23 > 24 bool point_in_polygon( vector<CMP>& ps, CMP p ) > 25 { > 26 bool in = false; > 27 for(int i=0; i<ps.size(); ++i) { > 28 CMP a = ps[i] - p; > 29 CMP b = ps[(i+1)%ps.size()] - p; > 30 if(a.imag() > b.imag()) swap(a,b); > 31 if(a.imag()<=0 && 0<b.imag()) { > 32 if( outer_prod(a,b) < 0 ) > 33 in = !in; > 34 } > 35 } > 36 return in; > 37 } > 38 > 39 class RedAndBluePoints { public: > 40 int find(vector <int> blueX, vector <int> blueY, vector <int> redX, vect > 41 { > 42 const int B = blueX.size(); > 43 const int R = redX.size(); > 44 > 45 int best = 0; > 46 for(int b_use=0; b_use<B; ++b_use) > 47 { > 48 vector<vector<int>> G(B); > 49 for(int b1=0; b1<B; ++b1) if(b1 != b_use) > 50 for(int b2=b1+1; b2<B; ++b2) if(b2 != b_use) { > 51 bool bad = false; > 52 > 53 vector<CMP> poly; > 54 poly.emplace_back(blueX[b_use], blueY[b_use]); > 55 poly.emplace_back(blueX[b1], blueY[b1]); > 56 poly.emplace_back(blueX[b2], blueY[b2]); > 57 for(int r=0; r<R; ++r) > 58 if(point_in_polygon(poly, CMP(redX[r], r > 59 { bad=true; break; } > 60 > 61 if(bad) { > 62 G[b1].push_back(b2); > 63 G[b2].push_back(b1); > 64 } > 65 } > 66 best = max(best, max_independent_set(G)); > 67 } > 68 return best; > 69 } > 70 > 71 int max_independent_set(const vector<vector<int>>& G) > 72 { > 73 const int N = G.size(); > 74 vector<LL> badmask(G.size()); > 75 for(int v=0; v<N; ++v) { > 76 LL x = 1LL<<v; > 77 for(int u: G[v]) > 78 x |= 1LL<<u; > 79 badmask[v] = x; > 80 } > 81 > 82 int best = 0; > 83 function<void(int,LL,int)> rec = [&](int v, LL rest, int cur) { > 84 if(best < cur) > 85 best = cur; > 86 if(rest == 0) > 87 return; > 88 if(cur + __builtin_popcountll(rest) <= best) > 89 return; > 90 > 91 LL r1 = rest &~ (1LL<<v); > 92 LL r2 = rest &~ badmask[v]; > 93 if(rest & (1LL<<v)) { > 94 if(r1 != r2) rec(v+1, r1, cur); > 95 rec(v+1, r2, cur+1); > 96 } else { > 97 rec(v+1, r1, cur); > 98 } > 99 }; > 100 rec(0, (1LL<<N)-1, 0); > 101 return best; > 102 } > 103 }; > 104 > 105 // BEGIN CUT HERE > 106 #include <ctime> > 107 double start_time; string timer() > 108 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 109 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 110 { os << "{ "; > 111 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 112 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 113 void verify_case(const int& Expected, const int& Received) { > 114 bool ok = (Expected == Received); > 115 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 116 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 117 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 118 #define END verify_case(_, RedAndBluePoints().find(blueX, blueY, redX, redY > 119 int main(){ > 120 > 121 CASE(0) > 122 int blueX_[] = {0,0,10,10}; > 123 vector <int> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); > 124 int blueY_[] = {0,10,0,10}; > 125 vector <int> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); > 126 int redX_[] = {100}; > 127 vector <int> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); > 128 int redY_[] = {120}; > 129 vector <int> redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_)); > 130 int _ = 4; > 131 END > 132 CASE(1) > 133 int blueX_[] = {0,0,10,10}; > 134 vector <int> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); > 135 int blueY_[] = {0,10,0,10}; > 136 vector <int> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); > 137 int redX_[] = {3}; > 138 vector <int> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); > 139 int redY_[] = {4}; > 140 vector <int> redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_)); > 141 int _ = 3; > 142 END > 143 CASE(2) > 144 int blueX_[] = {0,0,10,10}; > 145 vector <int> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); > 146 int blueY_[] = {0,10,0,10}; > 147 vector <int> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); > 148 int redX_[] = {3,6}; > 149 vector <int> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); > 150 int redY_[] = {2,7}; > 151 vector <int> redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_)); > 152 int _ = 2; > 153 END > 154 CASE(3) > 155 int blueX_[] = {0}; > 156 vector <int> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); > 157 int blueY_[] = {0}; > 158 vector <int> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); > 159 int redX_[] = {1}; > 160 vector <int> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); > 161 int redY_[] = {1}; > 162 vector <int> redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_)); > 163 int _ = 1; > 164 END > 165 CASE(4) > 166 int blueX_[] = {5, 6, 6}; > 167 vector <int> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); > 168 int blueY_[] = {9, 0, 5}; > 169 vector <int> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); > 170 int redX_[] = {7}; > 171 vector <int> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); > 172 int redY_[] = {6}; > 173 vector <int> redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_)); > 174 int _ = 3; > 175 END > 176 /* > 177 CASE(5) > 178 int blueX_[] = ; > 179 vector <int> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); > 180 int blueY_[] = ; > 181 vector <int> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); > 182 int redX_[] = ; > 183 vector <int> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); > 184 int redY_[] = ; > 185 vector <int> redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_)); > 186 int _ = ; > 187 END > 188 CASE(6) > 189 int blueX_[] = ; > 190 vector <int> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); > 191 int blueY_[] = ; > 192 vector <int> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); > 193 int redX_[] = ; > 194 vector <int> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); > 195 int redY_[] = ; > 196 vector <int> redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_)); > 197 int _ = ; > 198 END > 199 */ > 200 } > 201 // END CUT HERE
Added SRM/679/1C.cpp version [9a8c214df95651f4]
> 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 int MODVAL = 1000000007; > 23 class BagAndCards { public: > 24 int getHash(int n, int m, int x, int a, int b, int c, string isGood) > 25 { > 26 vector<vector<int>> count(n, vector<int>(m, 0)); > 27 for(int i=0; i<n; ++i) > 28 for(int j=0; j<m; ++j) { > 29 count[i][j] = x; > 30 x = int(((LL(x) * a + b) ^ c) % MODVAL); > 31 } > 32 > 33 int total_ans = 0; > 34 for(int i=0; i<n; ++i) > 35 { > 36 vector<LL> mult(m); > 37 for(int c1=0; c1<m; ++c1) > 38 for(int c2=0; c2<m; ++c2) > 39 if(isGood[c1+c2]=='Y') > 40 mult[c2] += count[i][c1]; > 41 for(int c=0; c<m; ++c) > 42 mult[c] %= MODVAL; > 43 > 44 for(int k=i+1; k<n; ++k) > 45 { > 46 LL ans = 0; > 47 for(int c=0; c<m; ++c) > 48 ans += count[k][c] * mult[c] % MODVAL; > 49 total_ans ^= int(ans % MODVAL); > 50 } > 51 } > 52 return total_ans; > 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(_, BagAndCards().getHash(n, m, x, a, b, c, isGood)) > 70 int main(){ > 71 > 72 CASE(0) > 73 int n = 2; > 74 int m = 4; > 75 int x = 1; > 76 int a = 1; > 77 int b = 0; > 78 int c = 0; > 79 string isGood = "NNYYNYN"; > 80 int _ = 9; > 81 END > 82 CASE(1) > 83 int n = 3; > 84 int m = 5; > 85 int x = 1; > 86 int a = 1; > 87 int b = 1; > 88 int c = 2; > 89 string isGood = "NNYYNYNYN"; > 90 int _ = 1532; > 91 END > 92 CASE(2) > 93 int n = 10; > 94 int m = 20; > 95 int x = 111; > 96 int a = 222; > 97 int b = 333; > 98 int c = 444; > 99 string isGood = "NNNNNYYYNNNYYYYYYNNYYYYNNNNYNNYYYNNNYYN" ; > 100 int _ = 450750683; > 101 END > 102 CASE(3) > 103 int n = 2; > 104 int m = 2; > 105 int x = 1; > 106 int a = 1; > 107 int b = 0; > 108 int c = 0; > 109 string isGood = "NNY"; > 110 int _ = 1; > 111 END > 112 /* > 113 CASE(4) > 114 int n = ; > 115 int m = ; > 116 int x = ; > 117 int a = ; > 118 int b = ; > 119 int c = ; > 120 string isGood = ; > 121 int _ = ; > 122 END > 123 CASE(5) > 124 int n = ; > 125 int m = ; > 126 int x = ; > 127 int a = ; > 128 int b = ; > 129 int c = ; > 130 string isGood = ; > 131 int _ = ; > 132 END > 133 */ > 134 } > 135 // END CUT HERE
Added lib/graph/maxIndependentSet.cpp version [d654c32e904bdfb1]
> 1 //------------------------------------------------------------- > 2 // Bruteforuce O(2^V) search with trivial edagari. > 3 // > 4 // |V| must be <= 63 > 5 // > 6 // Verified by > 7 // - SRM 679 Div1 Lv2 > 8 //------------------------------------------------------------- > 9 > 10 int max_independent_set(const vector<vector<int>>& G) > 11 { > 12 const int N = G.size(); > 13 vector<LL> badmask(G.size()); > 14 for(int v=0; v<N; ++v) { > 15 LL x = 1LL<<v; > 16 for(int u: G[v]) > 17 x |= 1LL<<u; > 18 badmask[v] = x; > 19 } > 20 > 21 int best = 0; > 22 function<void(int,LL,int)> rec = [&](int v, LL rest, int cur) { > 23 if(best < cur) > 24 best = cur; > 25 if(rest == 0) > 26 return; > 27 if(cur + __builtin_popcountll(rest) <= best) > 28 return; > 29 > 30 LL r1 = rest &~ (1LL<<v); > 31 LL r2 = rest &~ badmask[v]; > 32 if(rest & (1LL<<v)) { > 33 if(r1 != r2) rec(v+1, r1, cur); > 34 rec(v+1, r2, cur+1); > 35 } else { > 36 rec(v+1, r1, cur); > 37 } > 38 }; > 39 rec(0, (1LL<<N)-1, 0); > 40 return best; > 41 }