Overview
| SHA1 Hash: | 5cb1f42e864d6db1f6675a6b9dff7289beb9e84b |
|---|---|
| Date: | 2016-02-23 01:50:11 |
| User: | kinaba |
| Comment: | 680 |
| 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/680-U/1A.cpp version [c04d9fe9cff300c9]
> 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 BearFair { public: > 23 string isFair(int n, int b, vector <int> upTo, vector <int> quantity) > 24 { > 25 return isFair_bool(n, b, upTo, quantity) ? "fair" : "unfair"; > 26 } > 27 > 28 bool isFair_bool(int n, int b, vector <int> upTo, vector <int> quantity) > 29 { > 30 set<pair<int,int>> uqs; > 31 for(int i=0; i<upTo.size(); ++i) > 32 uqs.emplace(upTo[i], quantity[i]); > 33 uqs.emplace(b, n); > 34 vector<pair<int,int>> uq(uqs.begin(), uqs.end()); > 35 > 36 int LastU=0, LastQ=0; > 37 set<pair<int,int>> Cand; > 38 Cand.emplace(0, 0); > 39 > 40 for(auto& uqi: uq) { > 41 int u = uqi.first; > 42 int q = uqi.second; > 43 if(LastQ>q || (u==LastU && q!=LastQ)) > 44 return false; > 45 > 46 int Do = (u-LastU)/2 + ((u-LastU)%2==1 && u%2==1 ? 1 : 0 > 47 int De = (u-LastU)/2 + ((u-LastU)%2==1 && u%2==0 ? 1 : 0 > 48 int Dq = q - LastQ; > 49 if(Dq > Do+De) > 50 return false; > 51 > 52 LastU=u, LastQ=q; > 53 if(Dq == 0) > 54 continue; > 55 > 56 set<pair<int,int>> neo; > 57 for(auto c: Cand) { > 58 int o = c.first; > 59 int e = c.second; > 60 > 61 for(int oo=0; oo<=Do && oo<=Dq; ++oo) { > 62 int ee = Dq - oo; > 63 if(0<=ee && ee<=De && o+oo<=n/2 && e+ee< > 64 neo.emplace(o+oo, e+ee); > 65 } > 66 } > 67 } > 68 Cand = std::move(neo); > 69 } > 70 > 71 return Cand.count(make_pair(n/2, n/2)) > 0; > 72 } > 73 }; > 74 > 75 // BEGIN CUT HERE > 76 #include <ctime> > 77 double start_time; string timer() > 78 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 79 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 80 { os << "{ "; > 81 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 82 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 83 void verify_case(const string& Expected, const string& Received) { > 84 bool ok = (Expected == Received); > 85 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 86 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 87 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 88 #define END verify_case(_, BearFair().isFair(n, b, upTo, quantity));} > 89 int main(){ > 90 > 91 CASE(0) > 92 int n = 4; > 93 int b = 6; > 94 int upTo_[] = {3,6}; > 95 vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_)); > 96 int quantity_[] = {2,4}; > 97 vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*q > 98 string _ = "fair"; > 99 END > 100 CASE(1) > 101 int n = 4; > 102 int b = 6; > 103 int upTo_[] = {3,6}; > 104 vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_)); > 105 int quantity_[] = {2,3}; > 106 vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*q > 107 string _ = "unfair"; > 108 END > 109 CASE(2) > 110 int n = 2; > 111 int b = 6; > 112 int upTo_[] = {1,2,3}; > 113 vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_)); > 114 int quantity_[] = {1,1,2}; > 115 vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*q > 116 string _ = "unfair"; > 117 END > 118 CASE(3) > 119 int n = 50; > 120 int b = 1000; > 121 int upTo_[] = {736,205,264,235,273,40,901,37,900,424,122,517,820,402,669 > 122 186,970,231,321,902,606,24,451,585,823,270,361,292,128,521,689,683,270,726,980,6 > 123 vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_)); > 124 int quantity_[] = {35,9,9,9,9,3,46,3,46,18,7,25,39,18,32,9,20,49,37,49,7 > 125 vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*q > 126 string _ = "fair"; > 127 END > 128 CASE(4) > 129 int n = 4; > 130 int b = 1000; > 131 int upTo_[] = {400,600}; > 132 vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_)); > 133 int quantity_[] = {4,0}; > 134 vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*q > 135 string _ = "unfair"; > 136 END > 137 /* > 138 CASE(5) > 139 int n = ; > 140 int b = ; > 141 int upTo_[] = ; > 142 vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_)); > 143 int quantity_[] = ; > 144 vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*q > 145 string _ = ; > 146 END > 147 CASE(6) > 148 int n = ; > 149 int b = ; > 150 int upTo_[] = ; > 151 vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_)); > 152 int quantity_[] = ; > 153 vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*q > 154 string _ = ; > 155 END > 156 */ > 157 } > 158 // END CUT HERE
Added SRM/680-U/1B.cpp version [e83ccc45d7b07b3f]
> 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 BearSpans { public: > 23 vector <int> findAnyGraph(int n, int m, int k) > 24 { > 25 if(k>29 || (1<<k)>n) > 26 return vector<int>(1, -1); > 27 > 28 // generate basic > 29 vector<int> ans = gen_base(1, 1<<k); > 30 for(int p=1, v=(1<<k)+1; v<=n; p=v++) { > 31 ans.push_back(p); > 32 ans.push_back(v); > 33 } > 34 > 35 vector<vector<bool>> used(n+1, vector<bool>(n+1)); > 36 for(int i=0; i<ans.size(); i+=2) { > 37 used[ans[i]][ans[i+1]] = true; > 38 used[ans[i+1]][ans[i]] = true; > 39 } > 40 > 41 for(int s=1; s<=n && ans.size()<2*m; ++s) > 42 for(int e=s+1; e<=n && ans.size()<2*m; ++e) > 43 if(!used[s][e]) { > 44 ans.push_back(s); > 45 ans.push_back(e); > 46 } > 47 > 48 return ans; > 49 } > 50 > 51 vector<int> gen_base(int vS, int vE) > 52 { > 53 if(vS+1 == vE) { > 54 vector<int> ans; > 55 ans.push_back(vS); > 56 ans.push_back(vE); > 57 return ans; > 58 } > 59 > 60 int vM1 = vS + (vE-vS+1)/2 -1; > 61 int vM2 = vS + (vE-vS+1)/2; > 62 vector<int> a = gen_base(vS, vM1); > 63 vector<int> b = gen_base(vM2, vE); > 64 a.insert(a.end(), b.begin(), b.end()); > 65 a.push_back(vM1); > 66 a.push_back(vM2); > 67 return a; > 68 } > 69 }; > 70 > 71 // BEGIN CUT HERE > 72 struct UnionFind > 73 { > 74 vector<int> uf, sz; > 75 int nc; > 76 > 77 UnionFind(int N): uf(N), sz(N,1), nc(N) > 78 { for(int i=0; i<N; ++i) uf[i] = i; } > 79 int size() > 80 { return nc; } > 81 int size(int a) > 82 { return sz[Find(a)]; } > 83 int Find(int a) > 84 { return uf[a]==a ? a : uf[a]=Find(uf[a]); } > 85 // Semi-compression w.o. recursion. > 86 //{ while(uf[a] != a) a=uf[a]=uf[uf[a]]; return a; } > 87 bool Union(int a, int b) > 88 { > 89 a = Find(a); > 90 b = Find(b); > 91 if( a != b ) > 92 { > 93 if( sz[a] >= sz[b] ) swap(a, b); > 94 uf[a] = b; > 95 sz[b] += sz[a]; > 96 --nc; > 97 } > 98 return (a!=b); > 99 } > 100 }; > 101 > 102 int verify(vector<int> ans) > 103 { > 104 int m = ans.size() / 2; > 105 int n = *max_element(ans.begin(), ans.end()); > 106 if(n == -1) > 107 return -1; > 108 vector<tuple<int,int,int>> cft; > 109 for(int i=0; i<m; ++i) > 110 cft.emplace_back(i+1, ans[2*i+0]-1, ans[2*i+1]-1); > 111 vector<bool> added(cft.size()); > 112 > 113 UnionFind uf(n); > 114 int LoopCount=0; > 115 while(uf.size() > 1) { > 116 vector<int> to_add; > 117 vector<bool> done(n); > 118 > 119 for(int e=0; e<cft.size(); ++e) if(!added[e]) { > 120 int a = uf.Find(get<1>(cft[e])); > 121 int b = uf.Find(get<2>(cft[e])); > 122 if(a!=b) { > 123 if(!done[a] || !done[b]) { > 124 to_add.push_back(e); > 125 done[a] = true; > 126 done[b] = true; > 127 } > 128 } > 129 } > 130 > 131 for(int e: to_add) { > 132 added[e] = true; > 133 uf.Union(get<1>(cft[e]), get<2>(cft[e])); > 134 } > 135 > 136 LoopCount++; > 137 } > 138 return LoopCount; > 139 } > 140 > 141 #include <ctime> > 142 double start_time; string timer() > 143 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 144 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 145 { os << "{ "; > 146 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 147 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 148 void verify_case(const vector <int>& Expected, const vector <int>& Received) { > 149 > 150 bool ok = (verify(Expected) == verify(Received)); > 151 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 152 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 153 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 154 #define END verify_case(_, BearSpans().findAnyGraph(n, m, k));} > 155 int main(){ > 156 > 157 CASE(0) > 158 int n = 17; > 159 int m = 22; > 160 int k = 1; > 161 int __[] = {1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 9, 1, 10, 1, 11 > 162 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 163 END > 164 CASE(1) > 165 int n = 9; > 166 int m = 12; > 167 int k = 3; > 168 int __[] = {6, 5, 7, 6, 1, 2, 3, 4, 8, 9, 3, 5, 7, 4, 1, 9, 6, 2, 6, 1, > 169 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 170 END > 171 CASE(2) > 172 int n = 9; > 173 int m = 12; > 174 int k = 7; > 175 int __[] = {-1 }; > 176 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 177 END > 178 CASE(3) > 179 int n = 1000; > 180 int m = 999; > 181 int k = 970; > 182 int __[] = {-1 }; > 183 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 184 END > 185 CASE(4) > 186 int n = 2; > 187 int m = 1; > 188 int k = 1; > 189 int __[] = {1, 2 }; > 190 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 191 END > 192 CASE(5) > 193 int n = 3; > 194 int m = 2; > 195 int k = 1; > 196 int __[] = {1, 2, 1, 3 }; > 197 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 198 END > 199 CASE(6) > 200 int n = 3; > 201 int m = 3; > 202 int k = 2; > 203 int __[] = {-1 }; > 204 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 205 END > 206 /* > 207 CASE(7) > 208 int n = ; > 209 int m = ; > 210 int k = ; > 211 int __[] = ; > 212 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 213 END > 214 CASE(8) > 215 int n = ; > 216 int m = ; > 217 int k = ; > 218 int __[] = ; > 219 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 220 END > 221 */ > 222 > 223 } > 224 // END CUT HERE