Artifact Content
Not logged in

Artifact bf5480b3673212596456818a7b5027b4fcc2bbfa


#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 NeverAskHerAge { public:
	vector <int> possibleSolution(int n, vector <int> id1, vector <int> id2, vector <string> op, vector <string> rl, vector <int> val)
	{
		// !!!Being a geek, Jiro has to perfer 0-origin numbering!!!
		for(auto& g: id1) --g;
		for(auto& g: id2) --g;

		for(auto& s: rl) {if(s=="<=") s="L"; if(s==">=") s="G";}

		// check obviously false conditions.
		for(int i=0; i<id1.size(); ++i) if(rl[i]=="=") {
			if(op[i]=="/") {
				if(val[i]==0)
					return vector<int>();
				continue;
			}
			if(val[i]%1000 != 0)
				return vector<int>();
			int v = val[i] / 1000;
			if(op[i]=="+" && (v<2 || v>200)) return vector<int>();
			if(op[i]=="-" && (v<-99 || v>99)) return vector<int>();
			if(op[i]=="*") {
				if(v<1 || 10000<v) return vector<int>();
				for(int p=2; p*p<=v; ++p)
					while(v%p==0)v/=p;
				if(v>100) return vector<int>();
			}
		}

		// Relevant constraints
		vector<set<int>> rel(n);
		for(int i=0; i<id1.size(); ++i) rel[id1[i]].insert(i);
		for(int i=0; i<id2.size(); ++i) rel[id2[i]].insert(i);

		// Try highly constrained girl first.
		vector<int> girls; for(int g=0; g<n; ++g) girls.push_back(g);
		sort(girls.begin(), girls.end(), [&](int g1, int g2){return rel[g1].size()>rel[g2].size();});

		const int UNDETERMINED = 0;
		vector<int> x(n, UNDETERMINED);
		function<bool(int)> rec;
		rec = [&](int gi){
			if(gi == n)
				return true;
			int g = girls[gi];
			for(int age=1; age<=100; ++age)
			{
				x[g] = age;
				bool bad = false;
				for(int i: rel[g]) if(x[id1[i]]!=UNDETERMINED && x[id2[i]]!=UNDETERMINED) {
					if(!ok(x[id1[i]], op[i][0], x[id2[i]], rl[i][0], val[i]))
						{bad=true; break;}
				} else {
					if(!ok_part(x[id1[i]], op[i][0], x[id2[i]], rl[i][0], val[i]))
						{bad=true; break;}
				}
				if(!bad && rec(gi+1))
					return true;
				x[g] = UNDETERMINED;
			}
			return false;
		};
		if(!rec(0)) return vector<int>();
		return x;
	}

	static bool ok(int x1, char op, int x2, char rl, int val)
	{
		switch(op) {
		case '+': return ok((x1+x2)*1000, rl, val);
		case '-': return ok((x1-x2)*1000, rl, val);
		case '*': return ok((x1*x2)*1000, rl, val);
		case '/': return ok((x1)*1000, rl, val*x2);
		}
		return false;
	}
	static bool ok(int x, char rel, int y)
	{
		if(rel=='<') return x < y;
		if(rel=='L') return x <= y;
		if(rel=='>') return x > y;
		if(rel=='G') return x >= y;
		if(rel=='=') return x == y;
		return false;
	}
	static bool ok_part(int x1, char op, int x2, char rl, int val)
	{
		switch(op) {
		case '+': return ok_part_plus(max(x1,x2), rl, val);
		case '-': return x1 ? ok_part_minusl(x1, rl, val)
					        : ok_part_minusr(x2, rl, val);
		case '*': return ok_part_mult(max(x1,x2), rl, val);
		case '/': return x1 ? ok_part_divl(x1, rl, val)
					        : ok_part_divr(x2, rl, val);
		}
		return true;
	}
	// (x + ?)*1000 rel y
	static bool ok_part_plus(int x, char rel, int y)
	{
		if(rel=='<') return (x+1)*1000 < y;
		if(rel=='L') return (x+1)*1000 <= y;
		if(rel=='>') return (x+100)*1000 > y;
		if(rel=='G') return (x+100)*1000 >= y;
		if(rel=='=') return (x+1)*1000<=y && y<=(x+100)*1000;
		return false;
	}
	// (x - ?)*1000 rel y
	static bool ok_part_minusl(int x, char rel, int y)
	{
		if(rel=='<') return (x-100)*1000 < y;
		if(rel=='L') return (x-100)*1000 <= y;
		if(rel=='>') return (x-1)*1000 > y;
		if(rel=='G') return (x-1)*1000 >= y;
		if(rel=='=') return (x-100)*1000<=y && y<=(x-1)*1000;
		return false;
	}
	// (? - x)*1000 rel y
	static bool ok_part_minusr(int x, char rel, int y)
	{
		if(rel=='<') return (1-x)*1000 < y;
		if(rel=='L') return (1-x)*1000 <= y;
		if(rel=='>') return (100-x)*1000 > y;
		if(rel=='G') return (100-x)*1000 >= y;
		if(rel=='=') return (1-x)*1000<=y && y<=(100-x)*1000;
		return false;
	}
	// (x * ?)*1000 rel y
	static bool ok_part_mult(int x, char rel, int y)
	{
		if(rel=='<') return (x*1)*1000 < y;
		if(rel=='L') return (x*1)*1000 <= y;
		if(rel=='>') return (x*100)*1000 > y;
		if(rel=='G') return (x*100)*1000 >= y;
		if(rel=='=') return (x*1)*1000<=y && y<=(x*100)*1000 && y%(x*1000)==0;
		return false;
	}
	// (x / ?)*1000 rel y
	static bool ok_part_divl(int x, char rel, int y)
	{
		if(rel=='<') return x*1000 < y*100;
		if(rel=='L') return x*1000 <= y*100;
		if(rel=='>') return x*1000 > y*1;
		if(rel=='G') return x*1000 >= y*1;
		if(rel=='=') return x*1000 <= y*100 && x*1000 >= y*1 && (x*1000%y==0);
		return false;
	}
	static bool ok_part_divr(int x, char rel, int y)
	{
		return true;
	}
};

// 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 vector <int>& Expected, const vector <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(_, NeverAskHerAge().possibleSolution(n, id1, id2, op, rl, val));}
int main(){

CASE(0)
	int n = 2; 
	int id1_[] = {1,1};
	  vector <int> id1(id1_, id1_+sizeof(id1_)/sizeof(*id1_)); 
	int id2_[] = {2,2};
	  vector <int> id2(id2_, id2_+sizeof(id2_)/sizeof(*id2_)); 
	string op_[] = {"+","*"};
	  vector <string> op(op_, op_+sizeof(op_)/sizeof(*op_)); 
	string rl_[] = {"=","="};
	  vector <string> rl(rl_, rl_+sizeof(rl_)/sizeof(*rl_)); 
	int val_[] = {10000,21000};
	  vector <int> val(val_, val_+sizeof(val_)/sizeof(*val_)); 
	int __[] = {3, 7 };
	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(1)
	int n = 7; 
	int id1_[] = {1,2,3,4,5,6};
	  vector <int> id1(id1_, id1_+sizeof(id1_)/sizeof(*id1_)); 
	int id2_[] = {2,3,4,5,6,7};
	  vector <int> id2(id2_, id2_+sizeof(id2_)/sizeof(*id2_)); 
	string op_[] = {"/","/","/","/","/","/"};
	  vector <string> op(op_, op_+sizeof(op_)/sizeof(*op_)); 
	string rl_[] = {"=","=","=","=","=","="};
	  vector <string> rl(rl_, rl_+sizeof(rl_)/sizeof(*rl_)); 
	int val_[] = {2000,2000,2000,2000,2000,2000};
	  vector <int> val(val_, val_+sizeof(val_)/sizeof(*val_)); 
	int __[] = {64, 32, 16, 8, 4, 2, 1 };
	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(2)
	int n = 2; 
	int id1_[] = {1,1};
	  vector <int> id1(id1_, id1_+sizeof(id1_)/sizeof(*id1_)); 
	int id2_[] = {2,2};
	  vector <int> id2(id2_, id2_+sizeof(id2_)/sizeof(*id2_)); 
	string op_[] = {"/","/"};
	  vector <string> op(op_, op_+sizeof(op_)/sizeof(*op_)); 
	string rl_[] = {">","<"};
	  vector <string> rl(rl_, rl_+sizeof(rl_)/sizeof(*rl_)); 
	int val_[] = {2621,2622};
	  vector <int> val(val_, val_+sizeof(val_)/sizeof(*val_)); 
	int __[] = {97, 37 };
	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(3)
	int n = 2; 
	int id1_[] = {1,1};
	  vector <int> id1(id1_, id1_+sizeof(id1_)/sizeof(*id1_)); 
	int id2_[] = {2,2};
	  vector <int> id2(id2_, id2_+sizeof(id2_)/sizeof(*id2_)); 
	string op_[] = {"*","+"};
	  vector <string> op(op_, op_+sizeof(op_)/sizeof(*op_)); 
	string rl_[] = {">","<="};
	  vector <string> rl(rl_, rl_+sizeof(rl_)/sizeof(*rl_)); 
	int val_[] = {6000,5000};
	  vector <int> val(val_, val_+sizeof(val_)/sizeof(*val_)); 
	vector <int> _; 
END
CASE(4)
	int n = 8; 
	int id1_[] = {1,3,5,7};
	  vector <int> id1(id1_, id1_+sizeof(id1_)/sizeof(*id1_)); 
	int id2_[] = {2,4,6,8};
	  vector <int> id2(id2_, id2_+sizeof(id2_)/sizeof(*id2_)); 
	string op_[] = {"+","-","*","/"};
	  vector <string> op(op_, op_+sizeof(op_)/sizeof(*op_)); 
	string rl_[] = {">=","<=","=","<="};
	  vector <string> rl(rl_, rl_+sizeof(rl_)/sizeof(*rl_)); 
	int val_[] = {200000,-99000,3589000,10};
	  vector <int> val(val_, val_+sizeof(val_)/sizeof(*val_)); 
	int __[] = {100, 100, 1, 100, 97, 37, 1, 100 };
	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(5)
	int n = 8; 
	int id1_[] = {7,1,3,4,4,3,7,2,3,6,4,4,6,5,2,8,2,2,7,6,2,2,8,6,5,6,5,4,4,8,6,1,3,5,5,4,3,7,4,8};
	  vector <int> id1(id1_, id1_+sizeof(id1_)/sizeof(*id1_)); 
	int id2_[] = {2,7,6,6,1,2,4,7,4,4,8,3,8,2,4,1,7,7,6,2,5,7,6,5,8,2,8,1,8,1,3,2,7,1,2,2,1,8,3,3};
	  vector <int> id2(id2_, id2_+sizeof(id2_)/sizeof(*id2_)); 
	string op_[] = {"/","*","/","-","*","+","*","+","/","+","-","+","*","+","/","*","-","/","-","*","/","/","/","*","/","+","+","*","*","-","-","*","+","+","+","-","+","/","+","*"};
	  vector <string> op(op_, op_+sizeof(op_)/sizeof(*op_)); 
	string rl_[] = {"<","<","<=",">","<","<=","<",">","<","<=","<=",">",">",">=","<",">","<","<",">",">=","<=","<","<=",">=","<=",">=",">=",">=","<=",">=","<=",">","<=","<",">","<=",">=","<","<=","<="};
	  vector <string> rl(rl_, rl_+sizeof(rl_)/sizeof(*rl_)); 
	int val_[] = {47636,5754558,3307,-41496,7043286,144246,5048203,72315,85384,182630,50604,9802,3843942,152392,60035,149684,94234,31209,-73898,195742,8383,71993,98477,4859384,74619,146266,60163,377564,5357728,-80040,72545,1088942,87517,192354,18629,45785,44151,95334,140360,1063484};
	  vector <int> val(val_, val_+sizeof(val_)/sizeof(*val_)); 
	int __[] = {56, 77, 19, 59, 77, 87, 43, 51 };
	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(6)
	int n = 8; 
	int id1_[] = {7,1,3,4,4,3,7,2,3,6,4,4,6,5,2,8,2,2,7,6,2,2,8,6,5,6,5,4,4,8,6,1,3,5,5,4,3,7,4,8};
	  vector <int> id1(id1_, id1_+sizeof(id1_)/sizeof(*id1_)); 
	int id2_[] = {2,7,6,6,1,2,4,7,4,4,8,3,8,2,4,1,7,7,6,2,5,7,6,5,8,2,8,1,8,1,3,2,7,1,2,2,1,8,3,3};
	  vector <int> id2(id2_, id2_+sizeof(id2_)/sizeof(*id2_)); 
	string op_[] = {"/","*","/","-","*","+","*","+","/","+","-","+","*","+","/","*","-","/","-","*","/","/","/","*","/","+","+","*","*","-","-","*","+","+","+","-","+","/","+","*"};
	  vector <string> op(op_, op_+sizeof(op_)/sizeof(*op_)); 
	string rl_[] = {"=","<","<=",">","<","<=","<",">","<","<=","<=",">",">",">=","<",">","<","<",">",">=","<=","<","<=",">=","<=",">=",">=",">=","<=",">=","<=",">","<=","<",">","<=",">=","<","<=","<="};
	  vector <string> rl(rl_, rl_+sizeof(rl_)/sizeof(*rl_)); 
	int val_[] = {2000,5754558,3307,-41496,7043286,144246,5048203,72315,85384,182630,50604,9802,3843942,152392,60035,149684,94234,31209,-73898,195742,8383,71993,98477,4859384,74619,146266,60163,377564,5357728,-80040,72545,1088942,87517,192354,18629,45785,44151,95334,140360,1063484};
	  vector <int> val(val_, val_+sizeof(val_)/sizeof(*val_)); 
	vector <int> _; 
END
/*
CASE(7)
	int n = ; 
	int id1_[] = ;
	  vector <int> id1(id1_, id1_+sizeof(id1_)/sizeof(*id1_)); 
	int id2_[] = ;
	  vector <int> id2(id2_, id2_+sizeof(id2_)/sizeof(*id2_)); 
	string op_[] = ;
	  vector <string> op(op_, op_+sizeof(op_)/sizeof(*op_)); 
	string rl_[] = ;
	  vector <string> rl(rl_, rl_+sizeof(rl_)/sizeof(*rl_)); 
	int val_[] = ;
	  vector <int> val(val_, val_+sizeof(val_)/sizeof(*val_)); 
	int __[] = ;
	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(8)
	int n = ; 
	int id1_[] = ;
	  vector <int> id1(id1_, id1_+sizeof(id1_)/sizeof(*id1_)); 
	int id2_[] = ;
	  vector <int> id2(id2_, id2_+sizeof(id2_)/sizeof(*id2_)); 
	string op_[] = ;
	  vector <string> op(op_, op_+sizeof(op_)/sizeof(*op_)); 
	string rl_[] = ;
	  vector <string> rl(rl_, rl_+sizeof(rl_)/sizeof(*rl_)); 
	int val_[] = ;
	  vector <int> val(val_, val_+sizeof(val_)/sizeof(*val_)); 
	int __[] = ;
	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
END
*/
}
// END CUT HERE