• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

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(), ans[i]);
           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() + i + 1);
           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) << " msec)"; return os.str(); }
          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 os; }
          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() << endl;
          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) << " msec)"; return os.str(); }
           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 os; }
           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() << endl;
           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(*gadgets_));
           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(*gadgets_));
           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(*gadgets_));
           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(*gadgets_));
           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(*gadgets_));
           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(*gadgets_));
          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(*gadgets_));
          108  + int __[] = ;
          109  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          110  +END
          111  +CASE(7)
          112  + int gadgets_[] = ;
          113  +   vector <int> gadgets(gadgets_, gadgets_+sizeof(gadgets_)/sizeof(*gadgets_));
          114  + int __[] = ;
          115  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          116  +END
          117  +*/
          118  +}
          119  +// END CUT HERE