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

Added SRM/662-U/1A.cpp version [8024e025ec6e49c3]

                                                                                        >     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  template<typename T>
                                                                                        >    23  struct DP2
                                                                                        >    24  {
                                                                                        >    25          const int N1, N2;
                                                                                        >    26          vector<T> data;
                                                                                        >    27          DP2(int N1, int N2, const T& t = T())
                                                                                        >    28                  : N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<
                                                                                        >    29          T& operator()(int i1, int i2)
                                                                                        >    30                  { return data[ (i1*N2)+i2 ]; }
                                                                                        >    31          void swap(DP2& rhs)
                                                                                        >    32                  { data.swap(rhs.data); }
                                                                                        >    33  };
                                                                                        >    34  
                                                                                        >    35  class FoxesOfTheRoundTable { public:
                                                                                        >    36          vector <int> minimalDifference(vector <int> h)
                                                                                        >    37          {
                                                                                        >    38                  const int N = h.size();
                                                                                        >    39                  vector<int> idx(N);
                                                                                        >    40                  for(int i=0; i<idx.size(); ++i) idx[i] = i;
                                                                                        >    41  
                                                                                        >    42                  sort(idx.begin(), idx.end(), [&](int a, int b) {
                                                                                        >    43                          return h[a] < h[b];
                                                                                        >    44                  });
                                                                                        >    45  
                                                                                        >    46                  vector<int> aa(1, 0), bb(1, 0);
                                                                                        >    47                  for(int k=1; k<N-1; ++k)
                                                                                        >    48                          (aa.back()<bb.back() ? aa : bb).push_back(k);
                                                                                        >    49                  vector<int> ans;
                                                                                        >    50                  for(auto a: aa)
                                                                                        >    51                          ans.push_back(idx[a]);
                                                                                        >    52                  bb.push_back(N-1);
                                                                                        >    53                  reverse(bb.begin(), bb.end());
                                                                                        >    54                  bb.pop_back();
                                                                                        >    55                  for(auto b: bb)
                                                                                        >    56                          ans.push_back(idx[b]);
                                                                                        >    57  
                                                                                        >    58                  return ans;
                                                                                        >    59          }
                                                                                        >    60  };
                                                                                        >    61  
                                                                                        >    62  // BEGIN CUT HERE
                                                                                        >    63  #include <ctime>
                                                                                        >    64  double start_time; string timer()
                                                                                        >    65   { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000)
                                                                                        >    66  template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
                                                                                        >    67   { os << "{ ";
                                                                                        >    68     for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
                                                                                        >    69     os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return 
                                                                                        >    70  void verify_case(const vector <int>& Expected, const vector <int>& Received) {
                                                                                        >    71   bool ok = (Expected == Received);
                                                                                        >    72   if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer()
                                                                                        >    73   cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
                                                                                        >    74  #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(
                                                                                        >    75  #define END      verify_case(_, FoxesOfTheRoundTable().minimalDifference(h));}
                                                                                        >    76  int main(){
                                                                                        >    77  
                                                                                        >    78  CASE(0)
                                                                                        >    79          int h_[] = {1,99,50,50};
                                                                                        >    80            vector <int> h(h_, h_+sizeof(h_)/sizeof(*h_));
                                                                                        >    81          int __[] = {0, 3, 1, 2 };
                                                                                        >    82            vector <int> _(__, __+sizeof(__)/sizeof(*__));
                                                                                        >    83  END
                                                                                        >    84  CASE(1)
                                                                                        >    85          int h_[] = {123,456,789};
                                                                                        >    86            vector <int> h(h_, h_+sizeof(h_)/sizeof(*h_));
                                                                                        >    87          int __[] = {0, 1, 2 };
                                                                                        >    88            vector <int> _(__, __+sizeof(__)/sizeof(*__));
                                                                                        >    89  END
                                                                                        >    90  CASE(2)
                                                                                        >    91          int h_[] = {10,30,40,50,60};
                                                                                        >    92            vector <int> h(h_, h_+sizeof(h_)/sizeof(*h_));
                                                                                        >    93          int __[] = {0, 1, 4, 3, 2 };
                                                                                        >    94            vector <int> _(__, __+sizeof(__)/sizeof(*__));
                                                                                        >    95  END
                                                                                        >    96  CASE(3)
                                                                                        >    97          int h_[] = {1,2,3,4,8,12,13,14 };
                                                                                        >    98            vector <int> h(h_, h_+sizeof(h_)/sizeof(*h_));
                                                                                        >    99          int __[] = {0, 1, 2, 3, 5, 6, 7, 4 };
                                                                                        >   100            vector <int> _(__, __+sizeof(__)/sizeof(*__));
                                                                                        >   101  END
                                                                                        >   102  CASE(4)
                                                                                        >   103          int h_[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 };
                                                                                        >   104            vector <int> h(h_, h_+sizeof(h_)/sizeof(*h_));
                                                                                        >   105          int __[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17
                                                                                        >   106            vector <int> _(__, __+sizeof(__)/sizeof(*__));
                                                                                        >   107  END
                                                                                        >   108  /*
                                                                                        >   109  CASE(5)
                                                                                        >   110          int h_[] = ;
                                                                                        >   111            vector <int> h(h_, h_+sizeof(h_)/sizeof(*h_));
                                                                                        >   112          int __[] = ;
                                                                                        >   113            vector <int> _(__, __+sizeof(__)/sizeof(*__));
                                                                                        >   114  END
                                                                                        >   115  CASE(6)
                                                                                        >   116          int h_[] = ;
                                                                                        >   117            vector <int> h(h_, h_+sizeof(h_)/sizeof(*h_));
                                                                                        >   118          int __[] = ;
                                                                                        >   119            vector <int> _(__, __+sizeof(__)/sizeof(*__));
                                                                                        >   120  END
                                                                                        >   121  */
                                                                                        >   122  }
                                                                                        >   123  // END CUT HERE