Overview
| SHA1 Hash: | d02edd33e29c70e84fcae5aee156efce090acb71 |
|---|---|
| Date: | 2018-06-03 14:50:33 |
| User: | kinaba |
| Comment: | tco18r2a |
| 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/TCO18-2A-U/1A.cpp version [c6752f18484b73a9]
> 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 ArithmeticSequenceDiv1 { public: > 23 int findMinCost(vector <int> x) > 24 { > 25 int best = 0x7fffffff; > 26 for (int i = 0; i < x.size(); ++i) { > 27 // x[i]: fixed > 28 for (int z = 0; z < 1000; ++z) { > 29 int ss[] = { -1,+1 }; > 30 for (int s : ss) { > 31 int cur_cost = 0; > 32 for (int k = 0; k < x.size(); ++k) { > 33 int v = x[i]+s*z*(k-i); > 34 cur_cost += abs(v - x[k]); > 35 } > 36 best = min(best, cur_cost); > 37 } > 38 } > 39 } > 40 return best; > 41 } > 42 }; > 43 > 44 // BEGIN CUT HERE > 45 #include <ctime> > 46 double start_time; string timer() > 47 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 48 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 49 { os << "{ "; > 50 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 51 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 52 void verify_case(const int& Expected, const int& Received) { > 53 bool ok = (Expected == Received); > 54 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 55 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 56 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 57 #define END verify_case(_, ArithmeticSequenceDiv1().findMinCost(x));} > 58 int main(){ > 59 > 60 CASE(0) > 61 int x_[] = {1,3,2}; > 62 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 63 int _ = 2; > 64 END > 65 CASE(1) > 66 int x_[] = {1,1,1,2,3,4,5}; > 67 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 68 int _ = 3; > 69 END > 70 CASE(2) > 71 int x_[] = {1,2,3,4}; > 72 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 73 int _ = 0; > 74 END > 75 CASE(3) > 76 int x_[] = {1,5,2,5}; > 77 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 78 int _ = 5; > 79 END > 80 CASE(4) > 81 int x_[] = {11,33,22}; > 82 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 83 int _ = 17; > 84 END > 85 CASE(5) > 86 int x_[] = {1, 3, 5, 7, 2, 4, 6}; > 87 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 88 int _ = 12; > 89 END > 90 CASE(6) > 91 int x_[] = {17,68,99,48,66,66,20,88,91,4,20,7,82,23,76,55,50,7,46,88,73, > 92 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 93 int _ = -1; > 94 END > 95 /* > 96 CASE(7) > 97 int x_[] = ; > 98 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 99 int _ = ; > 100 END > 101 */ > 102 } > 103 // END CUT HERE
Added SRM/TCO18-2A-U/1B.cpp version [541b463b7581621e]
> 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 MakingRegularGraph { public: > 23 vector <int> addEdges(int n, vector <int> x, vector <int> y) > 24 { > 25 vector<int> deg(n); > 26 for (int i = 0; i < x.size(); ++i) > 27 deg[x[i]]++, deg[y[i]]++; > 28 > 29 set<int> d0, d1; > 30 for (int v = 0; v < n; ++v) > 31 if (deg[v] == 0) d0.insert(v); > 32 else if (deg[v] == 1) d1.insert(v); > 33 map<int, int> d1e; > 34 for (int i = 0; i < x.size(); ++i) > 35 if (d1.count(x[i]) && d1.count(y[i])) { > 36 d1e[x[i]] = y[i]; > 37 d1e[y[i]] = x[i]; > 38 d1.erase(x[i]); > 39 d1.erase(y[i]); > 40 } > 41 > 42 #define BAD (((d0.size()==1||d0.size()==2) && d1.empty() && d1e. > 43 if(BAD) > 44 return vector<int>(1, -1); > 45 > 46 vector<bool> used(n*n); > 47 for (int i = 0; i < x.size(); ++i) > 48 used[x[i] * n + y[i]] = true; > 49 > 50 vector<int> ans; > 51 for(int v=0; v<n; ++v) > 52 for(int u=v+1; u<n; ++u) if(!used[v*n+u]) > 53 { > 54 if (d0.empty() && d1.empty() && d1e.empty()) > 55 break; > 56 > 57 bool bad = true; > 58 if (d0.count(v)) { > 59 d0.erase(v); > 60 if (d0.count(u)) { > 61 d0.erase(u); > 62 d1e[v] = u; > 63 d1e[u] = v; > 64 if (bad=BAD) { > 65 d0.insert(u); > 66 d1e.erase(v); > 67 d1e.erase(u); > 68 } > 69 } > 70 else if (d1.count(u)) { > 71 d1.erase(u); > 72 d1.insert(v); > 73 if (bad = BAD) { > 74 d1.insert(u); > 75 d1.erase(v); > 76 } > 77 } > 78 else if (d1e.count(u)) { > 79 int ut = d1e[u]; d1e.erase(u); > 80 d1.insert(v); > 81 if (bad = BAD) { > 82 d1e[u] = ut; > 83 d1.erase(v); > 84 } > 85 } > 86 if (bad) > 87 d0.insert(v); > 88 } > 89 else if (d1.count(v)) { > 90 d1.erase(v); > 91 if (d0.count(u)) { > 92 d0.erase(u); > 93 d1.insert(u); > 94 if (bad = BAD) { > 95 d0.insert(u); > 96 d1.erase(u); > 97 } > 98 } > 99 else if (d1.count(u)) { > 100 d1.erase(u); > 101 if (bad = BAD) { > 102 d1.insert(u); > 103 } > 104 } > 105 else if (d1e.count(u)) { > 106 int ut = d1e[u]; d1e.erase(u); > 107 if (bad = BAD) { > 108 d1e[u] = ut; > 109 } > 110 } > 111 if (bad) > 112 d1.insert(v); > 113 } > 114 else if (d1e.count(v)) { > 115 int vt = d1e[v]; d1e.erase(v); > 116 if (d0.count(u)) { > 117 d0.erase(u); > 118 d1.insert(u); > 119 if (bad = BAD) { > 120 d0.insert(u); > 121 d1.erase(u); > 122 } > 123 } > 124 else if (d1.count(u)) { > 125 d1.erase(u); > 126 if (bad = BAD) { > 127 d1.insert(u); > 128 } > 129 } > 130 else if (d1e.count(u)) { > 131 int ut = d1e[u]; d1e.erase(u); > 132 if (bad = BAD) { > 133 d1e[u] = ut; > 134 } > 135 } > 136 if (bad) > 137 d1e[v] = vt; > 138 } > 139 > 140 if(!bad) > 141 ans.push_back(v), ans.push_back(u); > 142 } > 143 > 144 return ans; > 145 } > 146 }; > 147 > 148 // BEGIN CUT HERE > 149 #include <ctime> > 150 double start_time; string timer() > 151 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 152 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 153 { os << "{ "; > 154 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 155 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 156 void verify_case(const vector <int>& Expected, const vector <int>& Received) { > 157 bool ok = (Expected == Received); > 158 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 159 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 160 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 161 #define END verify_case(_, MakingRegularGraph().addEdges(n, x, y));} > 162 int main(){ > 163 > 164 CASE(0) > 165 int n = 6; > 166 int x_[] = {0,2}; > 167 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 168 int y_[] = {2,3}; > 169 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 170 int __[] = {0, 1, 1, 4, 3, 5, 4, 5 }; > 171 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 172 END > 173 CASE(1) > 174 int n = 4; > 175 int x_[] = {1,2,1}; > 176 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 177 int y_[] = {2,3,3}; > 178 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 179 int __[] = {-1 }; > 180 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 181 END > 182 CASE(2) > 183 int n = 3; > 184 vector <int> x; > 185 vector <int> y; > 186 int __[] = {0, 1, 0, 2, 1, 2 }; > 187 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 188 END > 189 CASE(3) > 190 int n = 5; > 191 int x_[] = {0}; > 192 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 193 int y_[] = {4}; > 194 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 195 int __[] = {0, 1, 1, 2, 2, 3, 3, 4 }; > 196 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 197 END > 198 CASE(4) > 199 int n = 5; > 200 int x_[] = {2}; > 201 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 202 int y_[] = {3}; > 203 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 204 int __[] = {0, 1, 0, 2, 1, 4, 3, 4 }; > 205 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 206 END > 207 /* > 208 CASE(5) > 209 int n = ; > 210 int x_[] = ; > 211 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 212 int y_[] = ; > 213 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 214 int __[] = ; > 215 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 216 END > 217 CASE(6) > 218 int n = ; > 219 int x_[] = ; > 220 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 221 int y_[] = ; > 222 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 223 int __[] = ; > 224 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 225 END > 226 */ > 227 } > 228 // END CUT HERE