• 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)<(1<<28)); }
           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) << " msec)"; return os.str(); }
           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 os; }
           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() << endl;
           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, 18, 19 };
          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