3fe379f029 2012-11-30        kinaba: #include <iostream>
3fe379f029 2012-11-30        kinaba: #include <sstream>
3fe379f029 2012-11-30        kinaba: #include <iomanip>
3fe379f029 2012-11-30        kinaba: #include <vector>
3fe379f029 2012-11-30        kinaba: #include <string>
3fe379f029 2012-11-30        kinaba: #include <map>
3fe379f029 2012-11-30        kinaba: #include <set>
3fe379f029 2012-11-30        kinaba: #include <algorithm>
3fe379f029 2012-11-30        kinaba: #include <numeric>
3fe379f029 2012-11-30        kinaba: #include <iterator>
3fe379f029 2012-11-30        kinaba: #include <functional>
3fe379f029 2012-11-30        kinaba: #include <complex>
3fe379f029 2012-11-30        kinaba: #include <queue>
3fe379f029 2012-11-30        kinaba: #include <stack>
3fe379f029 2012-11-30        kinaba: #include <cmath>
3fe379f029 2012-11-30        kinaba: #include <cassert>
3fe379f029 2012-11-30        kinaba: using namespace std;
3fe379f029 2012-11-30        kinaba: typedef long long LL;
3fe379f029 2012-11-30        kinaba: typedef long double LD;
3fe379f029 2012-11-30        kinaba: typedef complex<LD> CMP;
3fe379f029 2012-11-30        kinaba: 
3fe379f029 2012-11-30        kinaba: class CirclesGame { public:
3fe379f029 2012-11-30        kinaba: 	string whoCanWin(vector <int> x, vector <int> y, vector <int> r)
3fe379f029 2012-11-30        kinaba: 	{
3fe379f029 2012-11-30        kinaba: 		vector< pair<int, pair<int,int> > > xyr;
3fe379f029 2012-11-30        kinaba: 		const int N = x.size();
3fe379f029 2012-11-30        kinaba: 		for(int i=0; i<N; ++i)
3fe379f029 2012-11-30        kinaba: 			xyr.push_back(make_pair(r[i], make_pair(x[i],y[i])));
3fe379f029 2012-11-30        kinaba: 		sort(xyr.begin(), xyr.end());
3fe379f029 2012-11-30        kinaba: 
3fe379f029 2012-11-30        kinaba: 		vector<int> parent(N, -1);
3fe379f029 2012-11-30        kinaba: 		for(int i=0; i<N; ++i) {
3fe379f029 2012-11-30        kinaba: 			for(int k=i+1; k<N; ++k) {
3fe379f029 2012-11-30        kinaba: 				int r1 = xyr[i].first;
3fe379f029 2012-11-30        kinaba: 				int x1 = xyr[i].second.first;
3fe379f029 2012-11-30        kinaba: 				int y1 = xyr[i].second.second;
3fe379f029 2012-11-30        kinaba: 				int r2 = xyr[k].first;
3fe379f029 2012-11-30        kinaba: 				int x2 = xyr[k].second.first;
3fe379f029 2012-11-30        kinaba: 				int y2 = xyr[k].second.second;
3fe379f029 2012-11-30        kinaba: 				if( (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) < r2*r2 )
3fe379f029 2012-11-30        kinaba: 					{parent[i] = k; break;}
3fe379f029 2012-11-30        kinaba: 			}
3fe379f029 2012-11-30        kinaba: 		}
3fe379f029 2012-11-30        kinaba: 		return solve(N, parent) ? "Bob" : "Alice";
3fe379f029 2012-11-30        kinaba: 	}
3fe379f029 2012-11-30        kinaba: 
3fe379f029 2012-11-30        kinaba: 	bool solve(int N, const vector<int>& p)
3fe379f029 2012-11-30        kinaba: 	{
3fe379f029 2012-11-30        kinaba: 		vector<int> r;
3fe379f029 2012-11-30        kinaba: 		vector< vector<int> > c(N);
3fe379f029 2012-11-30        kinaba: 		for(int i=0; i<N; ++i)
3fe379f029 2012-11-30        kinaba: 			if(p[i] == -1)
3fe379f029 2012-11-30        kinaba: 				r.push_back(i);
3fe379f029 2012-11-30        kinaba: 			else
3fe379f029 2012-11-30        kinaba: 				c[p[i]].push_back(i);
3fe379f029 2012-11-30        kinaba: 
3fe379f029 2012-11-30        kinaba: 		memo.assign(N, -1);
3fe379f029 2012-11-30        kinaba: 
3fe379f029 2012-11-30        kinaba: 		int XOR = 0;
3fe379f029 2012-11-30        kinaba: 		for(int i=0; i<r.size(); ++i) {
3fe379f029 2012-11-30        kinaba: 			int g = grundy(c, r[i]);
3fe379f029 2012-11-30        kinaba: 			XOR ^= g;
3fe379f029 2012-11-30        kinaba: 		}
3fe379f029 2012-11-30        kinaba: 		return XOR == 0;
3fe379f029 2012-11-30        kinaba: 	}
3fe379f029 2012-11-30        kinaba: 
3fe379f029 2012-11-30        kinaba: 	vector<int> memo;
3fe379f029 2012-11-30        kinaba: 	int grundy(const vector< vector<int> >& ch, int v)
3fe379f029 2012-11-30        kinaba: 	{
3fe379f029 2012-11-30        kinaba: 		if(memo[v]!=-1)
3fe379f029 2012-11-30        kinaba: 			return memo[v];
3fe379f029 2012-11-30        kinaba: 
3fe379f029 2012-11-30        kinaba: 		vector<int> next;
3fe379f029 2012-11-30        kinaba: 		rec(ch, v, 0, next);
3fe379f029 2012-11-30        kinaba: 		return memo[v] = mex(next);
3fe379f029 2012-11-30        kinaba: 	}
3fe379f029 2012-11-30        kinaba: 
3fe379f029 2012-11-30        kinaba: 	void rec(const vector< vector<int> >& ch, int v, int XOR_acc, vector<int>& next)
3fe379f029 2012-11-30        kinaba: 	{
3fe379f029 2012-11-30        kinaba: 		int XOR = XOR_acc;
3fe379f029 2012-11-30        kinaba: 		for(int i=0; i<ch[v].size(); ++i)
3fe379f029 2012-11-30        kinaba: 			XOR ^= grundy(ch, ch[v][i]);
3fe379f029 2012-11-30        kinaba: 
3fe379f029 2012-11-30        kinaba: 		// cut here.
3fe379f029 2012-11-30        kinaba: 		next.push_back(XOR);
3fe379f029 2012-11-30        kinaba: 		// go below.
3fe379f029 2012-11-30        kinaba: 		for(int i=0; i<ch[v].size(); ++i)
3fe379f029 2012-11-30        kinaba: 			rec(ch, ch[v][i], XOR^grundy(ch, ch[v][i]), next);
3fe379f029 2012-11-30        kinaba: 	}
3fe379f029 2012-11-30        kinaba: 
3fe379f029 2012-11-30        kinaba: 	int mex(vector<int>& next)
3fe379f029 2012-11-30        kinaba: 	{
3fe379f029 2012-11-30        kinaba: 		sort(next.begin(), next.end());
3fe379f029 2012-11-30        kinaba: 		for(int k=0; k<next.size(); ++k)
3fe379f029 2012-11-30        kinaba: 			if( k != next[k] )
3fe379f029 2012-11-30        kinaba: 				return k;
3fe379f029 2012-11-30        kinaba: 		return next.size();
3fe379f029 2012-11-30        kinaba: 	}
3fe379f029 2012-11-30        kinaba: };
3fe379f029 2012-11-30        kinaba: 
3fe379f029 2012-11-30        kinaba: // BEGIN CUT HERE
3fe379f029 2012-11-30        kinaba: #include <ctime>
3fe379f029 2012-11-30        kinaba: double start_time; string timer()
3fe379f029 2012-11-30        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
3fe379f029 2012-11-30        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
3fe379f029 2012-11-30        kinaba:  { os << "{ ";
3fe379f029 2012-11-30        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
3fe379f029 2012-11-30        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
3fe379f029 2012-11-30        kinaba: void verify_case(const string& Expected, const string& Received) {
3fe379f029 2012-11-30        kinaba:  bool ok = (Expected == Received);
3fe379f029 2012-11-30        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
3fe379f029 2012-11-30        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
3fe379f029 2012-11-30        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
3fe379f029 2012-11-30        kinaba: #define END	 verify_case(_, CirclesGame().whoCanWin(x, y, r));}
3fe379f029 2012-11-30        kinaba: int main(){
3fe379f029 2012-11-30        kinaba: 
3fe379f029 2012-11-30        kinaba: CASE(0)
3fe379f029 2012-11-30        kinaba: 	int x_[] = {0};
3fe379f029 2012-11-30        kinaba: 	  vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
3fe379f029 2012-11-30        kinaba: 	int y_[] = {0};
3fe379f029 2012-11-30        kinaba: 	  vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
3fe379f029 2012-11-30        kinaba: 	int r_[] = {1};
3fe379f029 2012-11-30        kinaba: 	  vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
3fe379f029 2012-11-30        kinaba: 	string _ = "Alice";
3fe379f029 2012-11-30        kinaba: END
3fe379f029 2012-11-30        kinaba: CASE(1)
3fe379f029 2012-11-30        kinaba: 	int x_[] = {0, 3};
3fe379f029 2012-11-30        kinaba: 	  vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
3fe379f029 2012-11-30        kinaba: 	int y_[] = {0, 0};
3fe379f029 2012-11-30        kinaba: 	  vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
3fe379f029 2012-11-30        kinaba: 	int r_[] = {1, 1};
3fe379f029 2012-11-30        kinaba: 	  vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
3fe379f029 2012-11-30        kinaba: 	string _ = "Bob";
3fe379f029 2012-11-30        kinaba: END
3fe379f029 2012-11-30        kinaba: CASE(2)
3fe379f029 2012-11-30        kinaba: 	int x_[] = {0, 0, 5};
3fe379f029 2012-11-30        kinaba: 	  vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
3fe379f029 2012-11-30        kinaba: 	int y_[] = {0, 0, 0};
3fe379f029 2012-11-30        kinaba: 	  vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
3fe379f029 2012-11-30        kinaba: 	int r_[] = {1, 2, 1};
3fe379f029 2012-11-30        kinaba: 	  vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
3fe379f029 2012-11-30        kinaba: 	string _ = "Alice";
3fe379f029 2012-11-30        kinaba: END
3fe379f029 2012-11-30        kinaba: CASE(3)
3fe379f029 2012-11-30        kinaba: 	int x_[] = {0, 0, 0, 10, 10, 20};
3fe379f029 2012-11-30        kinaba: 	  vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
3fe379f029 2012-11-30        kinaba: 	int y_[] = {0, 0, 0, 0, 0, 0};
3fe379f029 2012-11-30        kinaba: 	  vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
3fe379f029 2012-11-30        kinaba: 	int r_[] = {1, 2, 3, 1, 2, 1};
3fe379f029 2012-11-30        kinaba: 	  vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
3fe379f029 2012-11-30        kinaba: 	string _ = "Bob";
3fe379f029 2012-11-30        kinaba: END
3fe379f029 2012-11-30        kinaba: CASE(4)
3fe379f029 2012-11-30        kinaba: 	int x_[] = {10,20,30,40,50,60,70,80};
3fe379f029 2012-11-30        kinaba: 	  vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
3fe379f029 2012-11-30        kinaba: 	int y_[] = {8,7,6,5,4,3,2,1};
3fe379f029 2012-11-30        kinaba: 	  vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
3fe379f029 2012-11-30        kinaba: 	int r_[] = {2,2,2,2,2,2,2,2};
3fe379f029 2012-11-30        kinaba: 	  vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
3fe379f029 2012-11-30        kinaba: 	string _ = "Bob";
3fe379f029 2012-11-30        kinaba: END
3fe379f029 2012-11-30        kinaba: CASE(5)
3fe379f029 2012-11-30        kinaba: 	int x_[] = {0, 3, 6, 9, 12, -4747, -4777};
3fe379f029 2012-11-30        kinaba: 	  vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
3fe379f029 2012-11-30        kinaba: 	int y_[] = {-5858, -5858, -5858, -5858, -5858, 777, 777};
3fe379f029 2012-11-30        kinaba: 	  vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
3fe379f029 2012-11-30        kinaba: 	int r_[] = {58, 1, 1, 1, 1, 44, 8};
3fe379f029 2012-11-30        kinaba: 	  vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
3fe379f029 2012-11-30        kinaba: 	string _ = "Bob";
3fe379f029 2012-11-30        kinaba: END
3fe379f029 2012-11-30        kinaba: CASE(6)
3fe379f029 2012-11-30        kinaba: 	int x_[] = {5202, 5699, -7433, 5068, -9483, -684, -6593, 5108, -7813, 6823, 3267, -8222, -8547, 2878, 2413, 8557, 5149, 5073, -8638, -6108, 8097};
3fe379f029 2012-11-30        kinaba: 	  vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
3fe379f029 2012-11-30        kinaba: 	int y_[] = {8728, -7407, 4338, -8414, 7652, -3705, -984, 5976, -9180, -9119, 9301, 2398, 7915, 6205, 7665, 717, -9884, 11, -8579, -6903, -746};
3fe379f029 2012-11-30        kinaba: 	  vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
3fe379f029 2012-11-30        kinaba: 	int r_[] = {4196, 9303, 7152, 5875, 2943, 788, 502, 416, 1958, 3174, 182, 1256, 1147, 444, 979, 65, 1040, 1233, 438, 175, 1140};
3fe379f029 2012-11-30        kinaba: 	  vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
3fe379f029 2012-11-30        kinaba: 	string _ = "Alice";
3fe379f029 2012-11-30        kinaba: END
3fe379f029 2012-11-30        kinaba: /*
3fe379f029 2012-11-30        kinaba: CASE(7)
3fe379f029 2012-11-30        kinaba: 	int x_[] = ;
3fe379f029 2012-11-30        kinaba: 	  vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
3fe379f029 2012-11-30        kinaba: 	int y_[] = ;
3fe379f029 2012-11-30        kinaba: 	  vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
3fe379f029 2012-11-30        kinaba: 	int r_[] = ;
3fe379f029 2012-11-30        kinaba: 	  vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
3fe379f029 2012-11-30        kinaba: 	string _ = ;
3fe379f029 2012-11-30        kinaba: END
3fe379f029 2012-11-30        kinaba: CASE(8)
3fe379f029 2012-11-30        kinaba: 	int x_[] = ;
3fe379f029 2012-11-30        kinaba: 	  vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
3fe379f029 2012-11-30        kinaba: 	int y_[] = ;
3fe379f029 2012-11-30        kinaba: 	  vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
3fe379f029 2012-11-30        kinaba: 	int r_[] = ;
3fe379f029 2012-11-30        kinaba: 	  vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
3fe379f029 2012-11-30        kinaba: 	string _ = ;
3fe379f029 2012-11-30        kinaba: END
3fe379f029 2012-11-30        kinaba: */
3fe379f029 2012-11-30        kinaba: }
3fe379f029 2012-11-30        kinaba: // END CUT HERE