EelAndRabbit.cpp

#include <iostream>
#include <ctime>
#include <vector>
#include <list>
#include <queue>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cassert>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iterator>
#include <fstream>
using namespace std;

typedef long long 		int64;
typedef vector<int> 		vi;
typedef string 			ST;
typedef stringstream 		SS;
typedef vector< vector<int> > 	vvi;
typedef pair<int,int> 		ii;
typedef vector<string> 		vs;
/*
#if __cplusplus > 199711L	// for g++0x, value of __cplusplus must be greater thana 199711L.
	#define tr(i, c)	for(auto i = begin(c); i != end(c); i++)
#else
	#define tr(i, c)	for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#endif
*/
#define endl		("\n")
#define tr(i, c)	for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define PI		M_PI
#define E 		M_E
#define	eps		1e-9

#define	Sf		scanf
#define	Pf		printf

#define forn(i, n)	for(int i = 0, lets_stop_here = (int)n; i <  lets_stop_here; i++)
#define forab(i, a, b)	for(int i = a, lets_stop_here = (int)b; i <= lets_stop_here; i++)
#define rep(i, a, b)	for(int i = a, lets_stop_here = (int)b; i >= lets_stop_here; i--)

#define	all(c)		(c).begin(), (c).end()
#define	cl(a, b)	memset(a, b, sizeof(a))
#define mp		make_pair
#define pb		push_back

#define	present(x, c)	((c).find(x) != (c).end())	//map & set//
#define	cpresent(x, c)	(find( (c).begin(), (c).end(), x) != (c).end())	//vector & list//

#define read(n)		scanf("%d", &n)
#define write(n)	printf("%d ", n)
#define writeln(n)	printf("%d\n", n)

#if (0)
	#define debug 
#else 
	#define debug(x)	cout << #x << " = " << x << "\n"
#endif

class EelAndRabbit
{
public:
	int getmax(vector <int> l, vector <int> t);
};

set <int> mergeSet(set <int> st1, set <int> st2) {
	set <int> ret;
	for(__typeof((st1).begin()) it = (st1).begin(); it != (st1).end(); it++) {
		ret.insert(*it);
	}
	for(__typeof((st2).begin()) it = (st2).begin(); it != (st2).end(); it++) {
		ret.insert(*it);
	}
	return ret;
}

int EelAndRabbit::getmax (vector <int> l, vector <int> t) 
{
	set <int> tmp;
	int N = l.size();
	for(int i = 0; i < N; i++) {
		tmp.insert(t[i]);
		tmp.insert(t[i] + l[i]);
	}
	vector <int> tm;
	for(__typeof((tmp).begin()) it = (tmp).begin(); it != (tmp).end(); it++) {
		tm.push_back(*it);
	}
/*
	for(__typeof((tm).begin()) it = (tm).begin(); it != (tm).end(); it++) {
		 printf("%d ", *it);
	}
	cout << "\n";
*/
	map <int, set <int> > grp;

	for(__typeof((tm).begin()) it = (tm).begin(); it != (tm).end(); it++) {
		int tt = *it;
		printf("tt = %d: ",tt );
		for(int i = 0; i < N; i++) {
			if(tt >= t[i] && tt <= t[i] + l[i]) {
				grp[tt].insert(i);
				printf("%d ", i);
			}
		}
		cout << "\n";
	}
	int ret = 0;

	for(__typeof((grp).begin()) it = (grp).begin(); it != (grp).end(); it++) {
		for(__typeof((grp).begin()) jt = (grp).begin(); jt != (grp).end(); jt++) {
			set <int> st = mergeSet(it->second, jt->second);
			ret = max(ret, (int)st.size());
		}
	}
	
	return ret;
}

// BEGIN KAWIGIEDIT TESTING
// Generated by KawigiEdit 2.1.8 (beta) modified by pivanof
#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool KawigiEdit_RunTest(int testNum, vector <int> p0, vector <int> p1, bool hasAnswer, int p2) {
	cout << "Test " << testNum << ": [" << "{";
	for (int i = 0; int(p0.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << p0[i];
	}
	cout << "}" << "," << "{";
	for (int i = 0; int(p1.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << p1[i];
	}
	cout << "}";
	cout << "]" << endl;
	EelAndRabbit *obj;
	int answer;
	obj = new EelAndRabbit();
	clock_t startTime = clock();
	answer = obj->getmax(p0, p1);
	clock_t endTime = clock();
	delete obj;
	bool res;
	res = true;
	cout << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;
	if (hasAnswer) {
		cout << "Desired answer:" << endl;
		cout << "\t" << p2 << endl;
	}
	cout << "Your answer:" << endl;
	cout << "\t" << answer << endl;
	if (hasAnswer) {
		res = answer == p2;
	}
	if (!res) {
		cout << "DOESN'T MATCH!!!!" << endl;
	} else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2) {
		cout << "FAIL the timeout" << endl;
		res = false;
	} else if (hasAnswer) {
		cout << "Match :-)" << endl;
	} else {
		cout << "OK, but is it right?" << endl;
	}
	cout << "" << endl;
	return res;
}
int main() {
	bool all_right;
	all_right = true;
	
	vector <int> p0;
	vector <int> p1;
	int p2;
	
	{
	// ----- test 0 -----
	int t0[] = {2,4,3,2,2,1,10};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {2,6,3,7,0,2,0};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	p2 = 6;
	all_right = KawigiEdit_RunTest(0, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 1 -----
	int t0[] = {1,1,1};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {2,0,4};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	p2 = 2;
	all_right = KawigiEdit_RunTest(1, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 2 -----
	int t0[] = {1};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {1};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	p2 = 1;
	all_right = KawigiEdit_RunTest(2, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 3 -----
	int t0[] = {8,2,1,10,8,6,3,1,2,5};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {17,27,26,11,1,27,23,12,11,13};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	p2 = 7;
	all_right = KawigiEdit_RunTest(3, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 4 -----
	int t0[] = {2,2,2};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {2,4,6 };
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	p2 = 3;
	all_right = KawigiEdit_RunTest(4, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	if (all_right) {
		cout << "You're a stud (at least on the example cases)!" << endl;
	} else {
		cout << "Some of the test cases had errors." << endl;
	}
	return 0;
}
// PROBLEM STATEMENT
// Rabbit went to a river to catch eels.
// All eels are currently swimming down the stream at the same speed.
// Rabbit is standing by the river, downstream from all the eels.
// 
// 
// Each point on the river has a coordinate.
// The coordinates increase as we go down the stream.
// Initially, Rabbit is standing at the origin, and all eels have non-positive coordinates.
// 
// 
// You are given two vector <int>s: l and t.
// These describe the current configuration of eels.
// The speed of each eel is 1 (one).
// For each i, the length of eel number i is l[i].
// The head of eel number i will arrive at the coordinate 0 precisely at the time t[i].
// Therefore, at any time T the eel number i has its head at the coordinate T-t[i], and its tail at the coordinate T-t[i]-l[i].
// 
// 
// Rabbit may only catch an eel when some part of the eel (between head and tail, inclusive) is at the same coordinate as the rabbit.
// Rabbit can catch eels at most twice.
// Each time he decides to catch eels, he may catch as many of the currently available eels as he wants.
// (That is, he can only catch eels that are in front of him at that instant, and he is allowed and able to catch multiple eels at once.)
// 
// 
// Return the maximal total number of eels Rabbit can catch.
// 
// DEFINITION
// Class:EelAndRabbit
// Method:getmax
// Parameters:vector <int>, vector <int>
// Returns:int
// Method signature:int getmax(vector <int> l, vector <int> t)
// 
// 
// CONSTRAINTS
// -l will contain between 1 and 50 elements, inclusive.
// -Each element of l will be between 1 and 1,000,000,000, inclusive.
// -l and t will contain the same number of elements.
// -Each element of t will be between 0 and 1,000,000,000, inclusive.
// 
// 
// EXAMPLES
// 
// 0)
// {2, 4, 3, 2, 2, 1, 10}
// {2, 6, 3, 7, 0, 2, 0}
// 
// Returns: 6
// 
// Rabbit can catch 6 eels in the following way:
// 
// At time 2, catch Eel 0, Eel 4, Eel 5, and Eel 6.
// At time 8, catch Eel 1 and Eel 3.
// 
// 
// 
// 1)
// {1, 1, 1}
// {2, 0, 4}
// 
// Returns: 2
// 
// No two eels are in front of Rabbit at the same time, so Rabbit can catch at most two eels.
// 
// 2)
// {1}
// {1}
// 
// Returns: 1
// 
// 
// 
// 3)
// {8, 2, 1, 10, 8, 6, 3, 1, 2, 5}
// {17, 27, 26, 11, 1, 27, 23, 12, 11, 13}
// 
// Returns: 7
// 
// 
// 
// END KAWIGIEDIT TESTING

//Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!