Overview
| SHA1 Hash: | a2cd9490f2d26df7c9a9d6aa775099b91597bbea |
|---|---|
| Date: | 2014-04-24 22:49:58 |
| User: | kinaba |
| Comment: | 617 |
| 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/617-U/1A.cpp version [54f465468b0ed373]
> 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 MyLongCake { public: > 23 int cut(int n) > 24 { > 25 const int N = n; > 26 > 27 vector<int> ps; > 28 for(int p=2; p<=n; ++p) > 29 { > 30 if(n==1) > 31 break; > 32 if(n%p==0) { > 33 ps.push_back(p); > 34 while(n%p==0) n/=p; > 35 } > 36 } > 37 > 38 int cnt = 0; > 39 for(int i=1; i<=N; ++i) > 40 { > 41 int cut = 0; > 42 for(int p : ps) > 43 if(i%p==0) > 44 cut = 1; > 45 cnt += cut; > 46 } > 47 return cnt; > 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 int& Expected, const int& Received) { > 60 bool ok = (Expected == Received); > 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(_, MyLongCake().cut(n));} > 65 int main(){ > 66 > 67 CASE(0) > 68 int n = 6; > 69 int _ = 4; > 70 END > 71 CASE(1) > 72 int n = 3; > 73 int _ = 1; > 74 END > 75 CASE(2) > 76 int n = 15; > 77 int _ = 7; > 78 END > 79 CASE(3) > 80 int n = 100000; > 81 int _ = 60000; > 82 END > 83 /* > 84 CASE(4) > 85 int n = ; > 86 int _ = ; > 87 END > 88 CASE(5) > 89 int n = ; > 90 int _ = ; > 91 END > 92 */ > 93 } > 94 // END CUT HERE
Added SRM/617-U/1B.cpp version [e715da187bfbeab0]
> 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 PieOrDolphin { public: > 23 vector <int> Distribute(vector <int> choice1, vector <int> choice2) > 24 { > 25 const int E = choice1.size(); > 26 > 27 typedef int EdgeID, Vert; > 28 vector< map<EdgeID,Vert> > G(50); > 29 for(int i=0; i<E; ++i) { > 30 int v = choice1[i]; > 31 int u = choice2[i]; > 32 G[v][i] = u; > 33 G[u][i] = v; > 34 } > 35 > 36 vector<int> ans(E); > 37 function<void(int)> remove_cycle = [&](int S) > 38 { > 39 function<bool(int)> dfs; > 40 vector<bool> used(E); > 41 stack<pair<EdgeID,int>> stk; > 42 dfs = [&](int v) { > 43 for(auto eu: G[v]) { > 44 EdgeID e = eu.first; > 45 Vert u = eu.second; > 46 if(used[e]) > 47 continue; > 48 used[e] = true; > 49 stk.emplace(e, choice1[e]==v ? 1 : 2); > 50 if(u == S) { > 51 // found > 52 while(!stk.empty()) { > 53 EdgeID ee = stk.top().fi > 54 int dir = stk.top().seco > 55 stk.pop(); > 56 ans[ee] = dir; > 57 for(int v=0; v<50; ++v) > 58 G[v].erase(ee); > 59 } > 60 return true; > 61 } else { > 62 if(dfs(u)) > 63 return true; > 64 stk.pop(); > 65 } > 66 } > 67 return false; > 68 }; > 69 while(dfs(S)) {} > 70 }; > 71 > 72 function<void(Vert)> remove_tree = [&](int S) > 73 { > 74 function<void(Vert,Vert,int)> rec; > 75 rec = [&](int v, int p, int d) { > 76 int size = G[v].size() - 1; > 77 int cnt = 0; > 78 int lim = (d==+1 ? size/2 : (size+1)/2); > 79 for(auto& eu: G[v]) > 80 { > 81 EdgeID e = eu.first; > 82 Vert u = eu.second; > 83 if(u==p) > 84 continue; > 85 > 86 if(cnt++ < lim) > 87 { > 88 ans[e] = choice1[e]==v ? 1 : 2; > 89 rec(u, v, -1); > 90 } > 91 else > 92 { > 93 ans[e] = choice1[e]==v ? 2 : 1; > 94 rec(u, v, +1); > 95 } > 96 } > 97 G[v].clear(); > 98 }; > 99 rec(S, -1, -1); > 100 }; > 101 > 102 for(int v=0; v<50; ++v) > 103 remove_cycle(v); > 104 for(int v=0; v<50; ++v) > 105 if(!G[v].empty()) > 106 remove_tree(v); > 107 return ans; > 108 } > 109 }; > 110 > 111 // BEGIN CUT HERE > 112 int score(vector <int> choice1, vector <int> choice2, vector<int> ans) { > 113 vector<int> s(50); > 114 for(int i=0; i<choice1.size(); ++i) { > 115 int u = choice1[i]; > 116 int v = choice2[i]; > 117 if(ans[i]==1) { > 118 s[u]++; > 119 s[v]--; > 120 } else { > 121 assert(ans[i]==2); > 122 s[u]--; > 123 s[v]++; > 124 } > 125 } > 126 int total = 0; > 127 for(int si : s) total += abs(si); > 128 return total; > 129 } > 130 #include <ctime> > 131 double start_time; string timer() > 132 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 133 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 134 { os << "{ "; > 135 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 136 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 137 void verify_case(int Expected, int Received) { > 138 bool ok = (Expected == Received); > 139 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 140 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 141 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 142 #define END verify_case(score(choice1,choice2,_), score(choice1,choice2,Pie > 143 int main(){ > 144 > 145 CASE(0) > 146 int choice1_[] = {10, 20, 10}; > 147 vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choic > 148 int choice2_[] = {20, 30, 20}; > 149 vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choic > 150 int __[] = {2, 2, 1 }; > 151 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 152 END > 153 CASE(1) > 154 int choice1_[] = {0, 0}; > 155 vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choic > 156 int choice2_[] = {1, 1}; > 157 vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choic > 158 int __[] = {2, 1 }; > 159 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 160 END > 161 CASE(2) > 162 int choice1_[] = {0, 1, 2, 3, 5, 6, 7, 8}; > 163 vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choic > 164 int choice2_[] = {8, 7, 6, 5, 3, 2, 1, 0}; > 165 vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choic > 166 int __[] = {2, 2, 2, 2, 2, 2, 2, 2 }; > 167 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 168 END > 169 CASE(3) > 170 int choice1_[] = {49, 0, 48, 1}; > 171 vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choic > 172 int choice2_[] = {3, 4, 5, 6}; > 173 vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choic > 174 int __[] = {2, 2, 2, 2 }; > 175 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 176 END > 177 CASE(4) > 178 int choice1_[] = {21,4,14,0,31,46,1,34,2,3,27,19,47,46,17,11,41,12,31,0, > 179 34,10,6,13,2,40,15,16,32,32,29,1,23,8,10,49,22,10,15,40,20,0,30,1,43,33,42,28,39 > 180 vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choic > 181 int choice2_[] = {25,5,39,20,44,47,11,49,42,17,25,15,23,11,32,17,24,4,11 > 182 7,8,32,12,0,39,30,8,39,23,9,8,34,34,37,5,1,24,23,0,29,11,42,29,40,24,18,37,1,21, > 183 vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choic > 184 int __[] = {2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 1, 2, 1, 2, 1, 1, 1, > 185 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 186 END > 187 /* > 188 CASE(5) > 189 int choice1_[] = ; > 190 vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choic > 191 int choice2_[] = ; > 192 vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choic > 193 int __[] = ; > 194 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 195 END > 196 CASE(6) > 197 int choice1_[] = ; > 198 vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choic > 199 int choice2_[] = ; > 200 vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choic > 201 int __[] = ; > 202 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 203 END > 204 */ > 205 } > 206 // END CUT HERE