Artifact Content
Not logged in

Artifact 4f1638dcf4f1be51f5d318e614d7b2d17e11985d


#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>
using namespace std;
typedef long long LL;
typedef long double LD;
typedef complex<LD> CMP;

class CirclesGame { public:
	string whoCanWin(vector <int> x, vector <int> y, vector <int> r)
	{
		vector< pair<int, pair<int,int> > > xyr;
		const int N = x.size();
		for(int i=0; i<N; ++i)
			xyr.push_back(make_pair(r[i], make_pair(x[i],y[i])));
		sort(xyr.begin(), xyr.end());

		vector<int> parent(N, -1);
		for(int i=0; i<N; ++i) {
			for(int k=i+1; k<N; ++k) {
				int r1 = xyr[i].first;
				int x1 = xyr[i].second.first;
				int y1 = xyr[i].second.second;
				int r2 = xyr[k].first;
				int x2 = xyr[k].second.first;
				int y2 = xyr[k].second.second;
				if( (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) < r2*r2 )
					{parent[i] = k; break;}
			}
		}
		return solve(N, parent) ? "Bob" : "Alice";
	}

	bool solve(int N, const vector<int>& p)
	{
		vector<int> r;
		vector< vector<int> > c(N);
		for(int i=0; i<N; ++i)
			if(p[i] == -1)
				r.push_back(i);
			else
				c[p[i]].push_back(i);

		memo.assign(N, -1);

		int XOR = 0;
		for(int i=0; i<r.size(); ++i) {
			int g = grundy(c, r[i]);
			XOR ^= g;
		}
		return XOR == 0;
	}

	vector<int> memo;
	int grundy(const vector< vector<int> >& ch, int v)
	{
		if(memo[v]!=-1)
			return memo[v];

		vector<int> next;
		rec(ch, v, 0, next);
		return memo[v] = mex(next);
	}

	void rec(const vector< vector<int> >& ch, int v, int XOR_acc, vector<int>& next)
	{
		int XOR = XOR_acc;
		for(int i=0; i<ch[v].size(); ++i)
			XOR ^= grundy(ch, ch[v][i]);

		// cut here.
		next.push_back(XOR);
		// go below.
		for(int i=0; i<ch[v].size(); ++i)
			rec(ch, ch[v][i], XOR^grundy(ch, ch[v][i]), next);
	}

	int mex(vector<int>& next)
	{
		sort(next.begin(), next.end());
		for(int k=0; k<next.size(); ++k)
			if( k != next[k] )
				return k;
		return next.size();
	}
};

// BEGIN CUT HERE
#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(const string& Expected, const string& 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(_, CirclesGame().whoCanWin(x, y, r));}
int main(){

CASE(0)
	int x_[] = {0};
	  vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 
	int y_[] = {0};
	  vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 
	int r_[] = {1};
	  vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_)); 
	string _ = "Alice"; 
END
CASE(1)
	int x_[] = {0, 3};
	  vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 
	int y_[] = {0, 0};
	  vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 
	int r_[] = {1, 1};
	  vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_)); 
	string _ = "Bob"; 
END
CASE(2)
	int x_[] = {0, 0, 5};
	  vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 
	int y_[] = {0, 0, 0};
	  vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 
	int r_[] = {1, 2, 1};
	  vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_)); 
	string _ = "Alice"; 
END
CASE(3)
	int x_[] = {0, 0, 0, 10, 10, 20};
	  vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 
	int y_[] = {0, 0, 0, 0, 0, 0};
	  vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 
	int r_[] = {1, 2, 3, 1, 2, 1};
	  vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_)); 
	string _ = "Bob"; 
END
CASE(4)
	int x_[] = {10,20,30,40,50,60,70,80};
	  vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 
	int y_[] = {8,7,6,5,4,3,2,1};
	  vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 
	int r_[] = {2,2,2,2,2,2,2,2};
	  vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_)); 
	string _ = "Bob"; 
END
CASE(5)
	int x_[] = {0, 3, 6, 9, 12, -4747, -4777};
	  vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 
	int y_[] = {-5858, -5858, -5858, -5858, -5858, 777, 777};
	  vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 
	int r_[] = {58, 1, 1, 1, 1, 44, 8};
	  vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_)); 
	string _ = "Bob"; 
END
CASE(6)
	int x_[] = {5202, 5699, -7433, 5068, -9483, -684, -6593, 5108, -7813, 6823, 3267, -8222, -8547, 2878, 2413, 8557, 5149, 5073, -8638, -6108, 8097};
	  vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 
	int y_[] = {8728, -7407, 4338, -8414, 7652, -3705, -984, 5976, -9180, -9119, 9301, 2398, 7915, 6205, 7665, 717, -9884, 11, -8579, -6903, -746};
	  vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 
	int r_[] = {4196, 9303, 7152, 5875, 2943, 788, 502, 416, 1958, 3174, 182, 1256, 1147, 444, 979, 65, 1040, 1233, 438, 175, 1140};
	  vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_)); 
	string _ = "Alice"; 
END
/*
CASE(7)
	int x_[] = ;
	  vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 
	int y_[] = ;
	  vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 
	int r_[] = ;
	  vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_)); 
	string _ = ; 
END
CASE(8)
	int x_[] = ;
	  vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 
	int y_[] = ;
	  vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 
	int r_[] = ;
	  vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_)); 
	string _ = ; 
END
*/
}
// END CUT HERE