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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 62 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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().first; 54 + int dir = stk.top().second; 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) << " msec)"; return os.str(); } 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 os; } 137 +void verify_case(int Expected, int Received) { 138 + bool ok = (Expected == Received); 139 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 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,PieOrDolphin().Distribute(choice1, choice2)));} 143 +int main(){ 144 + 145 +CASE(0) 146 + int choice1_[] = {10, 20, 10}; 147 + vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choice1_)); 148 + int choice2_[] = {20, 30, 20}; 149 + vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_)); 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(*choice1_)); 156 + int choice2_[] = {1, 1}; 157 + vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_)); 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(*choice1_)); 164 + int choice2_[] = {8, 7, 6, 5, 3, 2, 1, 0}; 165 + vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_)); 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(*choice1_)); 172 + int choice2_[] = {3, 4, 5, 6}; 173 + vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_)); 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,34,18,8,14,23,40,0,18,48,35,42,24,25,32,25,44,17,6,44,34,12,39,43,39,26, 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,28,4,38,11,5,1,47,12,0,22,20,33,33,34,18,8,23,6}; 180 + vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choice1_)); 181 + int choice2_[] = {25,5,39,20,44,47,11,49,42,17,25,15,23,11,32,17,24,4,11,47,27,41,40,0,49,27,5,28,6,11,18,0,17,1,0,32,45,28,17,5,13,40,40,25,33, 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,0,31,47,23,33,45,48,31,11,40,45,24,22,19,26,37,39}; 183 + vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_)); 184 + int __[] = {2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 1, 2, 1, 2, 1, 1, 1, 2, 2, 2, 1, 2, 2, 2, 1, 2, 2, 1, 1, 2, 2, 1, 2, 1, 2, 1, 1, 2, 2, 1, 1, 2, 1, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 1, 1, 2, 2, 1, 1, 1, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 2, 1 }; 185 + vector <int> _(__, __+sizeof(__)/sizeof(*__)); 186 +END 187 +/* 188 +CASE(5) 189 + int choice1_[] = ; 190 + vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choice1_)); 191 + int choice2_[] = ; 192 + vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_)); 193 + int __[] = ; 194 + vector <int> _(__, __+sizeof(__)/sizeof(*__)); 195 +END 196 +CASE(6) 197 + int choice1_[] = ; 198 + vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choice1_)); 199 + int choice2_[] = ; 200 + vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_)); 201 + int __[] = ; 202 + vector <int> _(__, __+sizeof(__)/sizeof(*__)); 203 +END 204 +*/ 205 +} 206 +// END CUT HERE