e3362a9488 2014-05-10        kinaba: #include <iostream>
e3362a9488 2014-05-10        kinaba: #include <sstream>
e3362a9488 2014-05-10        kinaba: #include <iomanip>
e3362a9488 2014-05-10        kinaba: #include <vector>
e3362a9488 2014-05-10        kinaba: #include <string>
e3362a9488 2014-05-10        kinaba: #include <map>
e3362a9488 2014-05-10        kinaba: #include <set>
e3362a9488 2014-05-10        kinaba: #include <algorithm>
e3362a9488 2014-05-10        kinaba: #include <numeric>
e3362a9488 2014-05-10        kinaba: #include <iterator>
e3362a9488 2014-05-10        kinaba: #include <functional>
e3362a9488 2014-05-10        kinaba: #include <complex>
e3362a9488 2014-05-10        kinaba: #include <queue>
e3362a9488 2014-05-10        kinaba: #include <stack>
e3362a9488 2014-05-10        kinaba: #include <cmath>
e3362a9488 2014-05-10        kinaba: #include <cassert>
e3362a9488 2014-05-10        kinaba: #include <tuple>
e3362a9488 2014-05-10        kinaba: using namespace std;
e3362a9488 2014-05-10        kinaba: typedef long long LL;
e3362a9488 2014-05-10        kinaba: typedef complex<double> CMP;
e3362a9488 2014-05-10        kinaba: 
e3362a9488 2014-05-10        kinaba: class MovingRooksDiv1 { public:
e3362a9488 2014-05-10        kinaba: 	vector <int> move(vector <int> Y1, vector <int> Y2)
e3362a9488 2014-05-10        kinaba: 	{
e3362a9488 2014-05-10        kinaba: 		const int N = Y1.size();
e3362a9488 2014-05-10        kinaba: 		vector<int> ans;
e3362a9488 2014-05-10        kinaba: 
e3362a9488 2014-05-10        kinaba: 		for(int i=0; i<N; ++i)
e3362a9488 2014-05-10        kinaba: 		{
e3362a9488 2014-05-10        kinaba: 			if(Y1[i] < Y2[i])
e3362a9488 2014-05-10        kinaba: 				return vector<int>(1, -1);
e3362a9488 2014-05-10        kinaba: 			else if(Y1[i] > Y2[i])
e3362a9488 2014-05-10        kinaba: 			{
e3362a9488 2014-05-10        kinaba: 				vector<int> idx;
e3362a9488 2014-05-10        kinaba: 				idx.push_back(i);
e3362a9488 2014-05-10        kinaba: 				for(int k=i+1;; ++k)
e3362a9488 2014-05-10        kinaba: 				{
e3362a9488 2014-05-10        kinaba: 					if(Y1[idx.back()] > Y1[k])
e3362a9488 2014-05-10        kinaba: 						idx.push_back(k);
e3362a9488 2014-05-10        kinaba: 					if(Y1[k] == Y2[i])
e3362a9488 2014-05-10        kinaba: 						break;
e3362a9488 2014-05-10        kinaba: 				}
e3362a9488 2014-05-10        kinaba: 				for(int k=idx.size()-2; k>=0; --k) {
e3362a9488 2014-05-10        kinaba: 					ans.push_back(idx[k]);
e3362a9488 2014-05-10        kinaba: 					ans.push_back(idx[k+1]);
e3362a9488 2014-05-10        kinaba: 					swap(Y1[idx[k]], Y1[idx[k+1]]);
e3362a9488 2014-05-10        kinaba: 				}
e3362a9488 2014-05-10        kinaba: 			}
e3362a9488 2014-05-10        kinaba: 		}
e3362a9488 2014-05-10        kinaba: 		if(ans.size() > 2500)
e3362a9488 2014-05-10        kinaba: 			ans.resize(2500);
e3362a9488 2014-05-10        kinaba: 		return ans;
e3362a9488 2014-05-10        kinaba: 	}
e3362a9488 2014-05-10        kinaba: };
e3362a9488 2014-05-10        kinaba: 
e3362a9488 2014-05-10        kinaba: // BEGIN CUT HERE
e3362a9488 2014-05-10        kinaba: #include <ctime>
e3362a9488 2014-05-10        kinaba: double start_time; string timer()
e3362a9488 2014-05-10        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
e3362a9488 2014-05-10        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
e3362a9488 2014-05-10        kinaba:  { os << "{ ";
e3362a9488 2014-05-10        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
e3362a9488 2014-05-10        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
e3362a9488 2014-05-10        kinaba: void verify_case(const vector <int>& Expected, const vector <int>& Received) {
e3362a9488 2014-05-10        kinaba:  bool ok = (Expected == Received);
e3362a9488 2014-05-10        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
e3362a9488 2014-05-10        kinaba:  cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
e3362a9488 2014-05-10        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
e3362a9488 2014-05-10        kinaba: #define END	 verify_case(_, MovingRooksDiv1().move(Y1, Y2));}
e3362a9488 2014-05-10        kinaba: int main(){
e3362a9488 2014-05-10        kinaba: 
e3362a9488 2014-05-10        kinaba: CASE(0)
e3362a9488 2014-05-10        kinaba: 	int Y1_[] = {0};
e3362a9488 2014-05-10        kinaba: 	  vector <int> Y1(Y1_, Y1_+sizeof(Y1_)/sizeof(*Y1_));
e3362a9488 2014-05-10        kinaba: 	int Y2_[] = {0};
e3362a9488 2014-05-10        kinaba: 	  vector <int> Y2(Y2_, Y2_+sizeof(Y2_)/sizeof(*Y2_));
e3362a9488 2014-05-10        kinaba: 	vector <int> _;
e3362a9488 2014-05-10        kinaba: END
e3362a9488 2014-05-10        kinaba: CASE(1)
e3362a9488 2014-05-10        kinaba: 	int Y1_[] = {1,0};
e3362a9488 2014-05-10        kinaba: 	  vector <int> Y1(Y1_, Y1_+sizeof(Y1_)/sizeof(*Y1_));
e3362a9488 2014-05-10        kinaba: 	int Y2_[] = {0,1};
e3362a9488 2014-05-10        kinaba: 	  vector <int> Y2(Y2_, Y2_+sizeof(Y2_)/sizeof(*Y2_));
e3362a9488 2014-05-10        kinaba: 	int __[] = {0, 1 };
e3362a9488 2014-05-10        kinaba: 	  vector <int> _(__, __+sizeof(__)/sizeof(*__));
e3362a9488 2014-05-10        kinaba: END
e3362a9488 2014-05-10        kinaba: CASE(2)
e3362a9488 2014-05-10        kinaba: 	int Y1_[] = {1,2,0};
e3362a9488 2014-05-10        kinaba: 	  vector <int> Y1(Y1_, Y1_+sizeof(Y1_)/sizeof(*Y1_));
e3362a9488 2014-05-10        kinaba: 	int Y2_[] = {2,0,1};
e3362a9488 2014-05-10        kinaba: 	  vector <int> Y2(Y2_, Y2_+sizeof(Y2_)/sizeof(*Y2_));
e3362a9488 2014-05-10        kinaba: 	int __[] = {-1 };
e3362a9488 2014-05-10        kinaba: 	  vector <int> _(__, __+sizeof(__)/sizeof(*__));
e3362a9488 2014-05-10        kinaba: END
e3362a9488 2014-05-10        kinaba: CASE(3)
e3362a9488 2014-05-10        kinaba: 	int Y1_[] = {2,1,0,3,5,4};
e3362a9488 2014-05-10        kinaba: 	  vector <int> Y1(Y1_, Y1_+sizeof(Y1_)/sizeof(*Y1_));
e3362a9488 2014-05-10        kinaba: 	int Y2_[] = {0,1,2,3,4,5};
e3362a9488 2014-05-10        kinaba: 	  vector <int> Y2(Y2_, Y2_+sizeof(Y2_)/sizeof(*Y2_));
e3362a9488 2014-05-10        kinaba: 	int __[] = {0, 1, 0, 2, 1, 2, 4, 5 };
e3362a9488 2014-05-10        kinaba: 	  vector <int> _(__, __+sizeof(__)/sizeof(*__));
e3362a9488 2014-05-10        kinaba: END
e3362a9488 2014-05-10        kinaba: CASE(4)
e3362a9488 2014-05-10        kinaba: 	int Y1_[] = {10,9,8,7,6,5,4,3,2,1,0};
e3362a9488 2014-05-10        kinaba: 	  vector <int> Y1(Y1_, Y1_+sizeof(Y1_)/sizeof(*Y1_));
e3362a9488 2014-05-10        kinaba: 	int Y2_[] = {0,1,2,3,4,5,6,7,8,9,10};
e3362a9488 2014-05-10        kinaba: 	  vector <int> Y2(Y2_, Y2_+sizeof(Y2_)/sizeof(*Y2_));
e3362a9488 2014-05-10        kinaba: 	int __[] = {0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8, 0, 9, 0, 10, 1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 9, 1, 10, 2, 3, 2, 4, 2, 5, 2, 6, 2, 7, 2, 8, 2, 9, 2, 10, 3, 4, 3, 5, 3, 6, 3, 7, 3, 8, 3, 9, 3, 10, 4, 5, 4, 6, 4, 7, 4, 8, 4, 9, 4, 10, 5, 6, 5, 7, 5, 8, 5, 9, 5, 10, 6, 7, 6, 8, 6, 9, 6, 10, 7, 8, 7, 9, 7, 10, 8, 9, 8, 10, 9, 10 };
e3362a9488 2014-05-10        kinaba: 	  vector <int> _(__, __+sizeof(__)/sizeof(*__));
e3362a9488 2014-05-10        kinaba: END
e3362a9488 2014-05-10        kinaba: CASE(5)
e3362a9488 2014-05-10        kinaba: int Y1_[] = {2,1,0};
e3362a9488 2014-05-10        kinaba: 	  vector <int> Y1(Y1_, Y1_+sizeof(Y1_)/sizeof(*Y1_));
e3362a9488 2014-05-10        kinaba: 	  int Y2_[] = {0,2,1};
e3362a9488 2014-05-10        kinaba: 	  vector <int> Y2(Y2_, Y2_+sizeof(Y2_)/sizeof(*Y2_));
e3362a9488 2014-05-10        kinaba: 	  int __[] = {123456789};
e3362a9488 2014-05-10        kinaba: 	  vector <int> _(__, __+sizeof(__)/sizeof(*__));
e3362a9488 2014-05-10        kinaba: END
e3362a9488 2014-05-10        kinaba: /*
e3362a9488 2014-05-10        kinaba: CASE(6)
e3362a9488 2014-05-10        kinaba: 	int Y1_[] = ;
e3362a9488 2014-05-10        kinaba: 	  vector <int> Y1(Y1_, Y1_+sizeof(Y1_)/sizeof(*Y1_));
e3362a9488 2014-05-10        kinaba: 	int Y2_[] = ;
e3362a9488 2014-05-10        kinaba: 	  vector <int> Y2(Y2_, Y2_+sizeof(Y2_)/sizeof(*Y2_));
e3362a9488 2014-05-10        kinaba: 	int __[] = ;
e3362a9488 2014-05-10        kinaba: 	  vector <int> _(__, __+sizeof(__)/sizeof(*__));
e3362a9488 2014-05-10        kinaba: END
e3362a9488 2014-05-10        kinaba: */
e3362a9488 2014-05-10        kinaba: }
e3362a9488 2014-05-10        kinaba: // END CUT HERE