a2cd9490f2 2014-04-24        kinaba: #include <iostream>
a2cd9490f2 2014-04-24        kinaba: #include <sstream>
a2cd9490f2 2014-04-24        kinaba: #include <iomanip>
a2cd9490f2 2014-04-24        kinaba: #include <vector>
a2cd9490f2 2014-04-24        kinaba: #include <string>
a2cd9490f2 2014-04-24        kinaba: #include <map>
a2cd9490f2 2014-04-24        kinaba: #include <set>
a2cd9490f2 2014-04-24        kinaba: #include <algorithm>
a2cd9490f2 2014-04-24        kinaba: #include <numeric>
a2cd9490f2 2014-04-24        kinaba: #include <iterator>
a2cd9490f2 2014-04-24        kinaba: #include <functional>
a2cd9490f2 2014-04-24        kinaba: #include <complex>
a2cd9490f2 2014-04-24        kinaba: #include <queue>
a2cd9490f2 2014-04-24        kinaba: #include <stack>
a2cd9490f2 2014-04-24        kinaba: #include <cmath>
a2cd9490f2 2014-04-24        kinaba: #include <cassert>
a2cd9490f2 2014-04-24        kinaba: #include <tuple>
a2cd9490f2 2014-04-24        kinaba: using namespace std;
a2cd9490f2 2014-04-24        kinaba: typedef long long LL;
a2cd9490f2 2014-04-24        kinaba: typedef complex<double> CMP;
a2cd9490f2 2014-04-24        kinaba: 
a2cd9490f2 2014-04-24        kinaba: class PieOrDolphin { public:
a2cd9490f2 2014-04-24        kinaba: 	vector <int> Distribute(vector <int> choice1, vector <int> choice2)
a2cd9490f2 2014-04-24        kinaba: 	{
a2cd9490f2 2014-04-24        kinaba: 		const int E = choice1.size();
a2cd9490f2 2014-04-24        kinaba: 
a2cd9490f2 2014-04-24        kinaba: 		typedef int EdgeID, Vert;
a2cd9490f2 2014-04-24        kinaba: 		vector< map<EdgeID,Vert> > G(50);
a2cd9490f2 2014-04-24        kinaba: 		for(int i=0; i<E; ++i) {
a2cd9490f2 2014-04-24        kinaba: 			int v = choice1[i];
a2cd9490f2 2014-04-24        kinaba: 			int u = choice2[i];
a2cd9490f2 2014-04-24        kinaba: 			G[v][i] = u;
a2cd9490f2 2014-04-24        kinaba: 			G[u][i] = v;
a2cd9490f2 2014-04-24        kinaba: 		}
a2cd9490f2 2014-04-24        kinaba: 
a2cd9490f2 2014-04-24        kinaba: 		vector<int> ans(E);
a2cd9490f2 2014-04-24        kinaba: 		function<void(int)> remove_cycle = [&](int S)
a2cd9490f2 2014-04-24        kinaba: 		{
a2cd9490f2 2014-04-24        kinaba: 			function<bool(int)> dfs;
a2cd9490f2 2014-04-24        kinaba: 			vector<bool> used(E);
a2cd9490f2 2014-04-24        kinaba: 			stack<pair<EdgeID,int>> stk;
a2cd9490f2 2014-04-24        kinaba: 			dfs = [&](int v) {
a2cd9490f2 2014-04-24        kinaba: 				for(auto eu: G[v]) {
a2cd9490f2 2014-04-24        kinaba: 					EdgeID e = eu.first;
a2cd9490f2 2014-04-24        kinaba: 					Vert   u = eu.second;
a2cd9490f2 2014-04-24        kinaba: 					if(used[e])
a2cd9490f2 2014-04-24        kinaba: 						continue;
a2cd9490f2 2014-04-24        kinaba: 					used[e] = true;
a2cd9490f2 2014-04-24        kinaba: 					stk.emplace(e, choice1[e]==v ? 1 : 2);
a2cd9490f2 2014-04-24        kinaba: 					if(u == S) {
a2cd9490f2 2014-04-24        kinaba: 						// found
a2cd9490f2 2014-04-24        kinaba: 						while(!stk.empty()) {
a2cd9490f2 2014-04-24        kinaba: 							EdgeID ee = stk.top().first;
a2cd9490f2 2014-04-24        kinaba: 							int dir = stk.top().second;
a2cd9490f2 2014-04-24        kinaba: 							stk.pop();
a2cd9490f2 2014-04-24        kinaba: 							ans[ee] = dir;
a2cd9490f2 2014-04-24        kinaba: 							for(int v=0; v<50; ++v)
a2cd9490f2 2014-04-24        kinaba: 								G[v].erase(ee);
a2cd9490f2 2014-04-24        kinaba: 						}
a2cd9490f2 2014-04-24        kinaba: 						return true;
a2cd9490f2 2014-04-24        kinaba: 					} else {
a2cd9490f2 2014-04-24        kinaba: 						if(dfs(u))
a2cd9490f2 2014-04-24        kinaba: 							return true;
a2cd9490f2 2014-04-24        kinaba: 						stk.pop();
a2cd9490f2 2014-04-24        kinaba: 					}
a2cd9490f2 2014-04-24        kinaba: 				}
a2cd9490f2 2014-04-24        kinaba: 				return false;
a2cd9490f2 2014-04-24        kinaba: 			};
a2cd9490f2 2014-04-24        kinaba: 			while(dfs(S)) {}
a2cd9490f2 2014-04-24        kinaba: 		};
a2cd9490f2 2014-04-24        kinaba: 
a2cd9490f2 2014-04-24        kinaba: 		function<void(Vert)> remove_tree = [&](int S)
a2cd9490f2 2014-04-24        kinaba: 		{
a2cd9490f2 2014-04-24        kinaba: 			function<void(Vert,Vert,int)> rec;
a2cd9490f2 2014-04-24        kinaba: 			rec = [&](int v, int p, int d) {
a2cd9490f2 2014-04-24        kinaba: 				int size = G[v].size() - 1;
a2cd9490f2 2014-04-24        kinaba: 				int cnt = 0;
a2cd9490f2 2014-04-24        kinaba: 				int lim = (d==+1 ? size/2 : (size+1)/2);
a2cd9490f2 2014-04-24        kinaba: 				for(auto& eu: G[v])
a2cd9490f2 2014-04-24        kinaba: 				{
a2cd9490f2 2014-04-24        kinaba: 					EdgeID e = eu.first;
a2cd9490f2 2014-04-24        kinaba: 					Vert u = eu.second;
a2cd9490f2 2014-04-24        kinaba: 					if(u==p)
a2cd9490f2 2014-04-24        kinaba: 						continue;
a2cd9490f2 2014-04-24        kinaba: 
a2cd9490f2 2014-04-24        kinaba: 					if(cnt++ < lim)
a2cd9490f2 2014-04-24        kinaba: 					{
a2cd9490f2 2014-04-24        kinaba: 						ans[e] = choice1[e]==v ? 1 : 2;
a2cd9490f2 2014-04-24        kinaba: 						rec(u, v, -1);
a2cd9490f2 2014-04-24        kinaba: 					}
a2cd9490f2 2014-04-24        kinaba: 					else
a2cd9490f2 2014-04-24        kinaba: 					{
a2cd9490f2 2014-04-24        kinaba: 						ans[e] = choice1[e]==v ? 2 : 1;
a2cd9490f2 2014-04-24        kinaba: 						rec(u, v, +1);
a2cd9490f2 2014-04-24        kinaba: 					}
a2cd9490f2 2014-04-24        kinaba: 				}
a2cd9490f2 2014-04-24        kinaba: 				G[v].clear();
a2cd9490f2 2014-04-24        kinaba: 			};
a2cd9490f2 2014-04-24        kinaba: 			rec(S, -1, -1);
a2cd9490f2 2014-04-24        kinaba: 		};
a2cd9490f2 2014-04-24        kinaba: 
a2cd9490f2 2014-04-24        kinaba: 		for(int v=0; v<50; ++v)
a2cd9490f2 2014-04-24        kinaba: 			remove_cycle(v);
a2cd9490f2 2014-04-24        kinaba: 		for(int v=0; v<50; ++v)
a2cd9490f2 2014-04-24        kinaba: 			if(!G[v].empty())
a2cd9490f2 2014-04-24        kinaba: 				remove_tree(v);
a2cd9490f2 2014-04-24        kinaba: 		return ans;
a2cd9490f2 2014-04-24        kinaba: 	}
a2cd9490f2 2014-04-24        kinaba: };
a2cd9490f2 2014-04-24        kinaba: 
a2cd9490f2 2014-04-24        kinaba: // BEGIN CUT HERE
a2cd9490f2 2014-04-24        kinaba: int score(vector <int> choice1, vector <int> choice2, vector<int> ans) {
a2cd9490f2 2014-04-24        kinaba: 	vector<int> s(50);
a2cd9490f2 2014-04-24        kinaba: 	for(int i=0; i<choice1.size(); ++i) {
a2cd9490f2 2014-04-24        kinaba: 		int u = choice1[i];
a2cd9490f2 2014-04-24        kinaba: 		int v = choice2[i];
a2cd9490f2 2014-04-24        kinaba: 		if(ans[i]==1) {
a2cd9490f2 2014-04-24        kinaba: 			s[u]++;
a2cd9490f2 2014-04-24        kinaba: 			s[v]--;
a2cd9490f2 2014-04-24        kinaba: 		} else {
a2cd9490f2 2014-04-24        kinaba: 			assert(ans[i]==2);
a2cd9490f2 2014-04-24        kinaba: 			s[u]--;
a2cd9490f2 2014-04-24        kinaba: 			s[v]++;
a2cd9490f2 2014-04-24        kinaba: 		}
a2cd9490f2 2014-04-24        kinaba: 	}
a2cd9490f2 2014-04-24        kinaba: 	int total = 0;
a2cd9490f2 2014-04-24        kinaba: 	for(int si : s) total += abs(si);
a2cd9490f2 2014-04-24        kinaba: 	return total;
a2cd9490f2 2014-04-24        kinaba: }
a2cd9490f2 2014-04-24        kinaba: #include <ctime>
a2cd9490f2 2014-04-24        kinaba: double start_time; string timer()
a2cd9490f2 2014-04-24        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
a2cd9490f2 2014-04-24        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
a2cd9490f2 2014-04-24        kinaba:  { os << "{ ";
a2cd9490f2 2014-04-24        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
a2cd9490f2 2014-04-24        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
a2cd9490f2 2014-04-24        kinaba: void verify_case(int Expected, int Received) {
a2cd9490f2 2014-04-24        kinaba:  bool ok = (Expected == Received);
a2cd9490f2 2014-04-24        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
a2cd9490f2 2014-04-24        kinaba:  cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
a2cd9490f2 2014-04-24        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
a2cd9490f2 2014-04-24        kinaba: #define END	 verify_case(score(choice1,choice2,_), score(choice1,choice2,PieOrDolphin().Distribute(choice1, choice2)));}
a2cd9490f2 2014-04-24        kinaba: int main(){
a2cd9490f2 2014-04-24        kinaba: 
a2cd9490f2 2014-04-24        kinaba: CASE(0)
a2cd9490f2 2014-04-24        kinaba: 	int choice1_[] = {10, 20, 10};
a2cd9490f2 2014-04-24        kinaba: 	  vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choice1_));
a2cd9490f2 2014-04-24        kinaba: 	int choice2_[] = {20, 30, 20};
a2cd9490f2 2014-04-24        kinaba: 	  vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_));
a2cd9490f2 2014-04-24        kinaba: 	int __[] = {2, 2, 1 };
a2cd9490f2 2014-04-24        kinaba: 	  vector <int> _(__, __+sizeof(__)/sizeof(*__));
a2cd9490f2 2014-04-24        kinaba: END
a2cd9490f2 2014-04-24        kinaba: CASE(1)
a2cd9490f2 2014-04-24        kinaba: 	int choice1_[] = {0, 0};
a2cd9490f2 2014-04-24        kinaba: 	  vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choice1_));
a2cd9490f2 2014-04-24        kinaba: 	int choice2_[] = {1, 1};
a2cd9490f2 2014-04-24        kinaba: 	  vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_));
a2cd9490f2 2014-04-24        kinaba: 	int __[] = {2, 1 };
a2cd9490f2 2014-04-24        kinaba: 	  vector <int> _(__, __+sizeof(__)/sizeof(*__));
a2cd9490f2 2014-04-24        kinaba: END
a2cd9490f2 2014-04-24        kinaba: CASE(2)
a2cd9490f2 2014-04-24        kinaba: 	int choice1_[] = {0, 1, 2, 3, 5, 6, 7, 8};
a2cd9490f2 2014-04-24        kinaba: 	  vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choice1_));
a2cd9490f2 2014-04-24        kinaba: 	int choice2_[] = {8, 7, 6, 5, 3, 2, 1, 0};
a2cd9490f2 2014-04-24        kinaba: 	  vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_));
a2cd9490f2 2014-04-24        kinaba: 	int __[] = {2, 2, 2, 2, 2, 2, 2, 2 };
a2cd9490f2 2014-04-24        kinaba: 	  vector <int> _(__, __+sizeof(__)/sizeof(*__));
a2cd9490f2 2014-04-24        kinaba: END
a2cd9490f2 2014-04-24        kinaba: CASE(3)
a2cd9490f2 2014-04-24        kinaba: 	int choice1_[] = {49, 0, 48, 1};
a2cd9490f2 2014-04-24        kinaba: 	  vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choice1_));
a2cd9490f2 2014-04-24        kinaba: 	int choice2_[] = {3, 4, 5, 6};
a2cd9490f2 2014-04-24        kinaba: 	  vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_));
a2cd9490f2 2014-04-24        kinaba: 	int __[] = {2, 2, 2, 2 };
a2cd9490f2 2014-04-24        kinaba: 	  vector <int> _(__, __+sizeof(__)/sizeof(*__));
a2cd9490f2 2014-04-24        kinaba: END
a2cd9490f2 2014-04-24        kinaba: CASE(4)
a2cd9490f2 2014-04-24        kinaba: 	int choice1_[] = {21,4,14,0,31,46,1,34,2,3,27,19,47,46,17,11,41,12,31,0,34,18,8,14,23,40,0,18,48,35,42,24,25,32,25,44,17,6,44,34,12,39,43,39,26,
a2cd9490f2 2014-04-24        kinaba: 34,10,6,13,2,40,15,16,32,32,29,1,23,8,10,49,22,10,15,40,20,0,30,1,43,33,42,28,39,28,4,38,11,5,1,47,12,0,22,20,33,33,34,18,8,23,6};
a2cd9490f2 2014-04-24        kinaba: 	  vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choice1_));
a2cd9490f2 2014-04-24        kinaba: 	int choice2_[] = {25,5,39,20,44,47,11,49,42,17,25,15,23,11,32,17,24,4,11,47,27,41,40,0,49,27,5,28,6,11,18,0,17,1,0,32,45,28,17,5,13,40,40,25,33,
a2cd9490f2 2014-04-24        kinaba: 7,8,32,12,0,39,30,8,39,23,9,8,34,34,37,5,1,24,23,0,29,11,42,29,40,24,18,37,1,21,0,31,47,23,33,45,48,31,11,40,45,24,22,19,26,37,39};
a2cd9490f2 2014-04-24        kinaba: 	  vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_));
a2cd9490f2 2014-04-24        kinaba: 	int __[] = {2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 1, 2, 1, 2, 1, 1, 1, 2, 2, 2, 1, 2, 2, 2, 1, 2, 2, 1, 1, 2, 2, 1, 2, 1, 2, 1, 1, 2, 2, 1, 1, 2, 1, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 1, 1, 2, 2, 1, 1, 1, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 2, 1 };
a2cd9490f2 2014-04-24        kinaba: 	  vector <int> _(__, __+sizeof(__)/sizeof(*__));
a2cd9490f2 2014-04-24        kinaba: END
a2cd9490f2 2014-04-24        kinaba: /*
a2cd9490f2 2014-04-24        kinaba: CASE(5)
a2cd9490f2 2014-04-24        kinaba: 	int choice1_[] = ;
a2cd9490f2 2014-04-24        kinaba: 	  vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choice1_));
a2cd9490f2 2014-04-24        kinaba: 	int choice2_[] = ;
a2cd9490f2 2014-04-24        kinaba: 	  vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_));
a2cd9490f2 2014-04-24        kinaba: 	int __[] = ;
a2cd9490f2 2014-04-24        kinaba: 	  vector <int> _(__, __+sizeof(__)/sizeof(*__));
a2cd9490f2 2014-04-24        kinaba: END
a2cd9490f2 2014-04-24        kinaba: CASE(6)
a2cd9490f2 2014-04-24        kinaba: 	int choice1_[] = ;
a2cd9490f2 2014-04-24        kinaba: 	  vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choice1_));
a2cd9490f2 2014-04-24        kinaba: 	int choice2_[] = ;
a2cd9490f2 2014-04-24        kinaba: 	  vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_));
a2cd9490f2 2014-04-24        kinaba: 	int __[] = ;
a2cd9490f2 2014-04-24        kinaba: 	  vector <int> _(__, __+sizeof(__)/sizeof(*__));
a2cd9490f2 2014-04-24        kinaba: END
a2cd9490f2 2014-04-24        kinaba: */
a2cd9490f2 2014-04-24        kinaba: }
a2cd9490f2 2014-04-24        kinaba: // END CUT HERE