ADDED SRM/TCO22-2A-U/1A.cpp Index: SRM/TCO22-2A-U/1A.cpp ================================================================== --- SRM/TCO22-2A-U/1A.cpp +++ SRM/TCO22-2A-U/1A.cpp @@ -0,0 +1,210 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long LL; +typedef complex CMP; + +class RearrangeAndIncrement { public: + vector change(int X, int Y) + { + vector ans; + to_one(X, &ans); + from_one(Y, &ans); + + vector a; + for (int i = 0; i < ans.size(); ++i) { + a.push_back(ans[i]); + for (;;) { + auto it = find(ans.begin() + i + 1, ans.end(), ans[i]); + if (it == ans.end()) break; + i = it - ans.begin(); + } + } + cerr << "!!!" << a.size() << endl; + return a; + } + + void to_one(int X, vector* ans) + { + ans->push_back(X); + while (X != 1) { + if (X % 10 != 0) { + X += 10 - X % 10; + ans->push_back(X); + } + + vector Xs = to_vec(X); + sort(Xs.rbegin(), Xs.rend()); + X = to_int(Xs); + ans->push_back(X); + } + } + + void from_one(int Y, vector* ans) + { + vector Ys = to_vec(Y); + + vector Xs(Ys.size(), 0); + Xs.back() = 1; + + one_to_base(to_int(Xs), ans); + for (int i=Ys.size()-1; i>=0; --i) { + if (count(Ys.begin(), Ys.begin() + i, 0) == i) { + // i + // 00001 + // 0000Y + if (i == 0) { + Xs[i] = Ys[i]; + ans->push_back(to_int(Xs)); + } + else { + while (Xs[i] != Ys[i]) { + for (int k = i - 1; k >= 1; --k) { + Xs[0] = 9; + ans->push_back(to_int(Xs)); + swap(Xs[0], Xs[k]); + ans->push_back(to_int(Xs)); + } + for (int k = i - 1; k >= 0; --k) + Xs[k] = 0; + Xs[i]++; + ans->push_back(to_int(Xs)); + } + } + } + else { + // i + // 00001 + // ****Y + Xs[0] = Ys[i]; + ans->push_back(to_int(Xs)); + rotate(Xs.begin(), Xs.begin() + 1, Xs.begin() + i + 1); + ans->push_back(to_int(Xs)); + } + } + } + + void one_to_base(int B, vector* ans) + { + int X = 1; + while(X != B) { + if (X == 1) { + X = 10; + ans->push_back(X); + } + else { + vector Xs = to_vec(X); + for (int i = Xs.size() - 1; i >= 1; --i) { + Xs[0] = 9; + ans->push_back(to_int(Xs)); + sort(Xs.begin(), Xs.end()); + ans->push_back(to_int(Xs)); + } + X *= 10; + ans->push_back(X); + } + } + } + + static vector to_vec(int x) { + vector xs; + while (x) { + xs.push_back(x % 10); + x /= 10; + } + return xs; + } + + static int to_int(const vector& xs) { + int x = 0; + int p = 1; + for (int d : xs) { + x += d * p; + p *= 10; + } + return x; + } +}; + +// BEGIN CUT HERE +#include +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const vector & Expected, const vector & Received) { + bool ok = (Expected == Received); + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); +#define END verify_case(_, RearrangeAndIncrement().change(X, Y));} +int main(){ + +CASE(0) + int X = 10234; + int Y = 1247; + int __[] = {10234, 1234, 1247 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(1) + int X = 10234; + int Y = 10248; + int __[] = {10234, 10244, 10248 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(2) + int X = 999997; + int Y = 1000001; + int __[] = {999997, 999998, 999999, 1000000, 1000001 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(3) + int X = 1000000; + int Y = 1000; + int __[] = {1000000, 1000 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(4) + int X = 1111111; + int Y = 1111232; + int __[] = {1111111, 1111122, 1111221, 1111232 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(5) + int X = 47; + int Y = 47; + int __[] = {47 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(6) + int X = 1; + int Y = 900000000; + int __[] = { -1 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(7) + int X = 111111111; + int Y = 900000000; + int __[] = { -1 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END + +} +// END CUT HERE ADDED SRM/TCO22-2A-U/1B-U.cpp Index: SRM/TCO22-2A-U/1B-U.cpp ================================================================== --- SRM/TCO22-2A-U/1B-U.cpp +++ SRM/TCO22-2A-U/1B-U.cpp @@ -0,0 +1,119 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long LL; +typedef complex CMP; + +class PlugStuffIn { public: + vector plug(vector gadgets) + { + vector idx; + for (int i = 0; i < gadgets.size(); ++i) + idx.push_back(i); + sort(idx.begin(), idx.end(), [&](int a, int b) { + return gadgets[a] > gadgets[b]; + }); + + vector ans(gadgets.size(), -1); + + deque s; + s.push_back(gadgets.size()); + for (int i : idx) + if (s.empty()) { + if (gadgets[i] == 0) + return vector(); + ans[i] = -1; + } + else { + ans[i] = s.front(); + s.pop_front(); + for (int k = 0; k < gadgets[i]; ++k) + s.push_back(i); + } + + return ans; + } +}; + +// BEGIN CUT HERE +#include +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const vector & Expected, const vector & Received) { + bool ok = (Expected == Received); + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); +#define END verify_case(_, PlugStuffIn().plug(gadgets));} +int main(){ + +CASE(0) + int gadgets_[] = {0}; + vector gadgets(gadgets_, gadgets_+sizeof(gadgets_)/sizeof(*gadgets_)); + int __[] = {1 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(1) + int gadgets_[] = {1, 1, 0, 1, 1, 1}; + vector gadgets(gadgets_, gadgets_+sizeof(gadgets_)/sizeof(*gadgets_)); + int __[] = {-1, -1, 4, -1, 6, -1 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(2) + int gadgets_[] = {1, 1, 0, 1, 1, 1, 0}; + vector gadgets(gadgets_, gadgets_+sizeof(gadgets_)/sizeof(*gadgets_)); + vector _; +END +CASE(3) + int gadgets_[] = {0, 0, 2, 0, 2}; + vector gadgets(gadgets_, gadgets_+sizeof(gadgets_)/sizeof(*gadgets_)); + int __[] = {2, 4, 5, 4, 2 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(4) + int gadgets_[] = {0, 3, 3}; + vector gadgets(gadgets_, gadgets_+sizeof(gadgets_)/sizeof(*gadgets_)); + int __[] = {3, 2, 1 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(5) + int gadgets_[] = {10, 20, 30, 40}; + vector gadgets(gadgets_, gadgets_+sizeof(gadgets_)/sizeof(*gadgets_)); + int __[] = {-1, 1, -1, -1 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +/* +CASE(6) + int gadgets_[] = ; + vector gadgets(gadgets_, gadgets_+sizeof(gadgets_)/sizeof(*gadgets_)); + int __[] = ; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(7) + int gadgets_[] = ; + vector gadgets(gadgets_, gadgets_+sizeof(gadgets_)/sizeof(*gadgets_)); + int __[] = ; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +*/ +} +// END CUT HERE