Artifact Content
Not logged in

Artifact e715da187bfbeab0406bd8544a0b86984b608303


#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <tuple>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

class PieOrDolphin { public:
	vector <int> Distribute(vector <int> choice1, vector <int> choice2)
	{
		const int E = choice1.size();

		typedef int EdgeID, Vert;
		vector< map<EdgeID,Vert> > G(50);
		for(int i=0; i<E; ++i) {
			int v = choice1[i];
			int u = choice2[i];
			G[v][i] = u;
			G[u][i] = v;
		}

		vector<int> ans(E);
		function<void(int)> remove_cycle = [&](int S)
		{
			function<bool(int)> dfs;
			vector<bool> used(E);
			stack<pair<EdgeID,int>> stk;
			dfs = [&](int v) {
				for(auto eu: G[v]) {
					EdgeID e = eu.first;
					Vert   u = eu.second;
					if(used[e])
						continue;
					used[e] = true;
					stk.emplace(e, choice1[e]==v ? 1 : 2);
					if(u == S) {
						// found
						while(!stk.empty()) {
							EdgeID ee = stk.top().first;
							int dir = stk.top().second;
							stk.pop();
							ans[ee] = dir;
							for(int v=0; v<50; ++v)
								G[v].erase(ee);
						}
						return true;
					} else {
						if(dfs(u))
							return true;
						stk.pop();
					}
				}
				return false;
			};
			while(dfs(S)) {}
		};

		function<void(Vert)> remove_tree = [&](int S)
		{
			function<void(Vert,Vert,int)> rec;
			rec = [&](int v, int p, int d) {
				int size = G[v].size() - 1;
				int cnt = 0;
				int lim = (d==+1 ? size/2 : (size+1)/2);
				for(auto& eu: G[v])
				{
					EdgeID e = eu.first;
					Vert u = eu.second;
					if(u==p)
						continue;

					if(cnt++ < lim)
					{
						ans[e] = choice1[e]==v ? 1 : 2;
						rec(u, v, -1);
					}
					else
					{
						ans[e] = choice1[e]==v ? 2 : 1;
						rec(u, v, +1);
					}
				}
				G[v].clear();
			};
			rec(S, -1, -1);
		};

		for(int v=0; v<50; ++v)
			remove_cycle(v);
		for(int v=0; v<50; ++v)
			if(!G[v].empty())
				remove_tree(v);
		return ans;
	}
};

// BEGIN CUT HERE
int score(vector <int> choice1, vector <int> choice2, vector<int> ans) {
	vector<int> s(50);
	for(int i=0; i<choice1.size(); ++i) {
		int u = choice1[i];
		int v = choice2[i];
		if(ans[i]==1) {
			s[u]++;
			s[v]--;
		} else {
			assert(ans[i]==2);
			s[u]--;
			s[v]++;
		}
	}
	int total = 0;
	for(int si : s) total += abs(si);
	return total;
}
#include <ctime>
double start_time; string timer()
 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(int Expected, int Received) {
 bool ok = (Expected == Received);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END	 verify_case(score(choice1,choice2,_), score(choice1,choice2,PieOrDolphin().Distribute(choice1, choice2)));}
int main(){

CASE(0)
	int choice1_[] = {10, 20, 10};
	  vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choice1_)); 
	int choice2_[] = {20, 30, 20};
	  vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_)); 
	int __[] = {2, 2, 1 };
	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(1)
	int choice1_[] = {0, 0};
	  vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choice1_)); 
	int choice2_[] = {1, 1};
	  vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_)); 
	int __[] = {2, 1 };
	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(2)
	int choice1_[] = {0, 1, 2, 3, 5, 6, 7, 8};
	  vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choice1_)); 
	int choice2_[] = {8, 7, 6, 5, 3, 2, 1, 0};
	  vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_)); 
	int __[] = {2, 2, 2, 2, 2, 2, 2, 2 };
	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(3)
	int choice1_[] = {49, 0, 48, 1};
	  vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choice1_)); 
	int choice2_[] = {3, 4, 5, 6};
	  vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_)); 
	int __[] = {2, 2, 2, 2 };
	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(4)
	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,
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};
	  vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choice1_)); 
	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,
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};
	  vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_)); 
	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 };
	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
END
/*
CASE(5)
	int choice1_[] = ;
	  vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choice1_)); 
	int choice2_[] = ;
	  vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_)); 
	int __[] = ;
	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(6)
	int choice1_[] = ;
	  vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choice1_)); 
	int choice2_[] = ;
	  vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_)); 
	int __[] = ;
	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
END
*/
}
// END CUT HERE