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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 55 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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,40,41,48,32,18,71,58,56,68,2,99,7,13,19,11,55,95,23,40,17,89,41,12,5,82,93,93,19,20,41,8,15,24,53,87,54,10,12,41,86,95,92,13,56,6,67,72,95,78,82,34,75,12,11,100,99,46,32,45,59,1,63,60,13,94,33,13,85,35,65,40,37,22,37,87,35,2,92,64}; 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.empty()) || (d0.empty() && d1.empty() && d1e.size()==2 && d1e.begin()->first==d1e.rbegin()->second)) 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 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