Artifact Content
Not logged in

Artifact c04d9fe9cff300c9519429736dc0b366dfb2bc1c


#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 BearFair { public:
	string isFair(int n, int b, vector <int> upTo, vector <int> quantity)
	{
		return isFair_bool(n, b, upTo, quantity) ? "fair" : "unfair";
	}

	bool isFair_bool(int n, int b, vector <int> upTo, vector <int> quantity)
	{
		set<pair<int,int>> uqs;
		for(int i=0; i<upTo.size(); ++i)
			uqs.emplace(upTo[i], quantity[i]);
		uqs.emplace(b, n);
		vector<pair<int,int>> uq(uqs.begin(), uqs.end());

		int LastU=0, LastQ=0;
		set<pair<int,int>> Cand;
		Cand.emplace(0, 0);

		for(auto& uqi: uq) {
			int u = uqi.first;
			int q = uqi.second;
			if(LastQ>q || (u==LastU && q!=LastQ))
				return false;

			int Do = (u-LastU)/2 + ((u-LastU)%2==1 && u%2==1 ? 1 : 0);
			int De = (u-LastU)/2 + ((u-LastU)%2==1 && u%2==0 ? 1 : 0);
			int Dq = q - LastQ;
			if(Dq > Do+De)
				return false;

			LastU=u, LastQ=q;
			if(Dq == 0)
				continue;

			set<pair<int,int>> neo;
			for(auto c: Cand) {
				int o = c.first;
				int e = c.second;

				for(int oo=0; oo<=Do && oo<=Dq; ++oo) {
					int ee = Dq - oo;
					if(0<=ee && ee<=De && o+oo<=n/2 && e+ee<=n/2) {
						neo.emplace(o+oo, e+ee);
					}
				}
			}
			Cand = std::move(neo);
		}

		return Cand.count(make_pair(n/2, n/2)) > 0;
	}
};

// 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(_, BearFair().isFair(n, b, upTo, quantity));}
int main(){

CASE(0)
	int n = 4; 
	int b = 6; 
	int upTo_[] = {3,6};
	  vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_)); 
	int quantity_[] = {2,4};
	  vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*quantity_)); 
	string _ = "fair"; 
END
CASE(1)
	int n = 4; 
	int b = 6; 
	int upTo_[] = {3,6};
	  vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_)); 
	int quantity_[] = {2,3};
	  vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*quantity_)); 
	string _ = "unfair"; 
END
CASE(2)
	int n = 2; 
	int b = 6; 
	int upTo_[] = {1,2,3};
	  vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_)); 
	int quantity_[] = {1,1,2};
	  vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*quantity_)); 
	string _ = "unfair"; 
END
CASE(3)
	int n = 50; 
	int b = 1000; 
	int upTo_[] = {736,205,264,235,273,40,901,37,900,424,122,517,820,402,669,279,455,921,774,923,107,936,484,171,248,
186,970,231,321,902,606,24,451,585,823,270,361,292,128,521,689,683,270,726,980,652,996,909,196,357};
	  vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_)); 
	int quantity_[] = {35,9,9,9,9,3,46,3,46,18,7,25,39,18,32,9,20,49,37,49,7,49,24,8,9,8,49,9,12,46,29,2,20,29,39,9,16,11,7,27,33,32,9,34,49,32,50,47,8,16};
	  vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*quantity_)); 
	string _ = "fair"; 
END
CASE(4)
	int n = 4; 
	int b = 1000; 
	int upTo_[] = {400,600};
	  vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_)); 
	int quantity_[] = {4,0};
	  vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*quantity_)); 
	string _ = "unfair"; 
END
/*
CASE(5)
	int n = ; 
	int b = ; 
	int upTo_[] = ;
	  vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_)); 
	int quantity_[] = ;
	  vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*quantity_)); 
	string _ = ; 
END
CASE(6)
	int n = ; 
	int b = ; 
	int upTo_[] = ;
	  vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_)); 
	int quantity_[] = ;
	  vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*quantity_)); 
	string _ = ; 
END
*/
}
// END CUT HERE