Overview
| SHA1 Hash: | cf074c940adb21e7883f5d0349cbb49f86f75cfd |
|---|---|
| Date: | 2022-05-21 17:51:56 |
| User: | kinaba |
| Comment: | TCO22 R2A |
| 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/TCO22-2A-U/1A.cpp version [083458483a56f720]
> 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 RearrangeAndIncrement { public: > 23 vector <int> change(int X, int Y) > 24 { > 25 vector<int> ans; > 26 to_one(X, &ans); > 27 from_one(Y, &ans); > 28 > 29 vector<int> a; > 30 for (int i = 0; i < ans.size(); ++i) { > 31 a.push_back(ans[i]); > 32 for (;;) { > 33 auto it = find(ans.begin() + i + 1, ans.end(), a > 34 if (it == ans.end()) break; > 35 i = it - ans.begin(); > 36 } > 37 } > 38 cerr << "!!!" << a.size() << endl; > 39 return a; > 40 } > 41 > 42 void to_one(int X, vector<int>* ans) > 43 { > 44 ans->push_back(X); > 45 while (X != 1) { > 46 if (X % 10 != 0) { > 47 X += 10 - X % 10; > 48 ans->push_back(X); > 49 } > 50 > 51 vector<int> Xs = to_vec(X); > 52 sort(Xs.rbegin(), Xs.rend()); > 53 X = to_int(Xs); > 54 ans->push_back(X); > 55 } > 56 } > 57 > 58 void from_one(int Y, vector<int>* ans) > 59 { > 60 vector<int> Ys = to_vec(Y); > 61 > 62 vector<int> Xs(Ys.size(), 0); > 63 Xs.back() = 1; > 64 > 65 one_to_base(to_int(Xs), ans); > 66 for (int i=Ys.size()-1; i>=0; --i) { > 67 if (count(Ys.begin(), Ys.begin() + i, 0) == i) { > 68 // i > 69 // 00001 > 70 // 0000Y > 71 if (i == 0) { > 72 Xs[i] = Ys[i]; > 73 ans->push_back(to_int(Xs)); > 74 } > 75 else { > 76 while (Xs[i] != Ys[i]) { > 77 for (int k = i - 1; k >= 1; --k) > 78 Xs[0] = 9; > 79 ans->push_back(to_int(Xs > 80 swap(Xs[0], Xs[k]); > 81 ans->push_back(to_int(Xs > 82 } > 83 for (int k = i - 1; k >= 0; --k) > 84 Xs[k] = 0; > 85 Xs[i]++; > 86 ans->push_back(to_int(Xs)); > 87 } > 88 } > 89 } > 90 else { > 91 // i > 92 // 00001 > 93 // ****Y > 94 Xs[0] = Ys[i]; > 95 ans->push_back(to_int(Xs)); > 96 rotate(Xs.begin(), Xs.begin() + 1, Xs.begin() + > 97 ans->push_back(to_int(Xs)); > 98 } > 99 } > 100 } > 101 > 102 void one_to_base(int B, vector<int>* ans) > 103 { > 104 int X = 1; > 105 while(X != B) { > 106 if (X == 1) { > 107 X = 10; > 108 ans->push_back(X); > 109 } > 110 else { > 111 vector<int> Xs = to_vec(X); > 112 for (int i = Xs.size() - 1; i >= 1; --i) { > 113 Xs[0] = 9; > 114 ans->push_back(to_int(Xs)); > 115 sort(Xs.begin(), Xs.end()); > 116 ans->push_back(to_int(Xs)); > 117 } > 118 X *= 10; > 119 ans->push_back(X); > 120 } > 121 } > 122 } > 123 > 124 static vector<int> to_vec(int x) { > 125 vector<int> xs; > 126 while (x) { > 127 xs.push_back(x % 10); > 128 x /= 10; > 129 } > 130 return xs; > 131 } > 132 > 133 static int to_int(const vector<int>& xs) { > 134 int x = 0; > 135 int p = 1; > 136 for (int d : xs) { > 137 x += d * p; > 138 p *= 10; > 139 } > 140 return x; > 141 } > 142 }; > 143 > 144 // BEGIN CUT HERE > 145 #include <ctime> > 146 double start_time; string timer() > 147 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 148 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 149 { os << "{ "; > 150 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 151 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 152 void verify_case(const vector <int>& Expected, const vector <int>& Received) { > 153 bool ok = (Expected == Received); > 154 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 155 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 156 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 157 #define END verify_case(_, RearrangeAndIncrement().change(X, Y));} > 158 int main(){ > 159 > 160 CASE(0) > 161 int X = 10234; > 162 int Y = 1247; > 163 int __[] = {10234, 1234, 1247 }; > 164 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 165 END > 166 CASE(1) > 167 int X = 10234; > 168 int Y = 10248; > 169 int __[] = {10234, 10244, 10248 }; > 170 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 171 END > 172 CASE(2) > 173 int X = 999997; > 174 int Y = 1000001; > 175 int __[] = {999997, 999998, 999999, 1000000, 1000001 }; > 176 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 177 END > 178 CASE(3) > 179 int X = 1000000; > 180 int Y = 1000; > 181 int __[] = {1000000, 1000 }; > 182 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 183 END > 184 CASE(4) > 185 int X = 1111111; > 186 int Y = 1111232; > 187 int __[] = {1111111, 1111122, 1111221, 1111232 }; > 188 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 189 END > 190 CASE(5) > 191 int X = 47; > 192 int Y = 47; > 193 int __[] = {47 }; > 194 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 195 END > 196 CASE(6) > 197 int X = 1; > 198 int Y = 900000000; > 199 int __[] = { -1 }; > 200 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 201 END > 202 CASE(7) > 203 int X = 111111111; > 204 int Y = 900000000; > 205 int __[] = { -1 }; > 206 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 207 END > 208 > 209 } > 210 // END CUT HERE
Added SRM/TCO22-2A-U/1B-U.cpp version [a4eff36568a9a1ce]
> 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 PlugStuffIn { public: > 23 vector <int> plug(vector <int> gadgets) > 24 { > 25 vector<int> idx; > 26 for (int i = 0; i < gadgets.size(); ++i) > 27 idx.push_back(i); > 28 sort(idx.begin(), idx.end(), [&](int a, int b) { > 29 return gadgets[a] > gadgets[b]; > 30 }); > 31 > 32 vector<int> ans(gadgets.size(), -1); > 33 > 34 deque<int> s; > 35 s.push_back(gadgets.size()); > 36 for (int i : idx) > 37 if (s.empty()) { > 38 if (gadgets[i] == 0) > 39 return vector<int>(); > 40 ans[i] = -1; > 41 } > 42 else { > 43 ans[i] = s.front(); > 44 s.pop_front(); > 45 for (int k = 0; k < gadgets[i]; ++k) > 46 s.push_back(i); > 47 } > 48 > 49 return ans; > 50 } > 51 }; > 52 > 53 // BEGIN CUT HERE > 54 #include <ctime> > 55 double start_time; string timer() > 56 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 57 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 58 { os << "{ "; > 59 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 60 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 61 void verify_case(const vector <int>& Expected, const vector <int>& Received) { > 62 bool ok = (Expected == Received); > 63 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 64 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 65 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 66 #define END verify_case(_, PlugStuffIn().plug(gadgets));} > 67 int main(){ > 68 > 69 CASE(0) > 70 int gadgets_[] = {0}; > 71 vector <int> gadgets(gadgets_, gadgets_+sizeof(gadgets_)/sizeof(*gadge > 72 int __[] = {1 }; > 73 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 74 END > 75 CASE(1) > 76 int gadgets_[] = {1, 1, 0, 1, 1, 1}; > 77 vector <int> gadgets(gadgets_, gadgets_+sizeof(gadgets_)/sizeof(*gadge > 78 int __[] = {-1, -1, 4, -1, 6, -1 }; > 79 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 80 END > 81 CASE(2) > 82 int gadgets_[] = {1, 1, 0, 1, 1, 1, 0}; > 83 vector <int> gadgets(gadgets_, gadgets_+sizeof(gadgets_)/sizeof(*gadge > 84 vector <int> _; > 85 END > 86 CASE(3) > 87 int gadgets_[] = {0, 0, 2, 0, 2}; > 88 vector <int> gadgets(gadgets_, gadgets_+sizeof(gadgets_)/sizeof(*gadge > 89 int __[] = {2, 4, 5, 4, 2 }; > 90 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 91 END > 92 CASE(4) > 93 int gadgets_[] = {0, 3, 3}; > 94 vector <int> gadgets(gadgets_, gadgets_+sizeof(gadgets_)/sizeof(*gadge > 95 int __[] = {3, 2, 1 }; > 96 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 97 END > 98 CASE(5) > 99 int gadgets_[] = {10, 20, 30, 40}; > 100 vector <int> gadgets(gadgets_, gadgets_+sizeof(gadgets_)/sizeof(*gadge > 101 int __[] = {-1, 1, -1, -1 }; > 102 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 103 END > 104 /* > 105 CASE(6) > 106 int gadgets_[] = ; > 107 vector <int> gadgets(gadgets_, gadgets_+sizeof(gadgets_)/sizeof(*gadge > 108 int __[] = ; > 109 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 110 END > 111 CASE(7) > 112 int gadgets_[] = ; > 113 vector <int> gadgets(gadgets_, gadgets_+sizeof(gadgets_)/sizeof(*gadge > 114 int __[] = ; > 115 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 116 END > 117 */ > 118 } > 119 // END CUT HERE