fbe763b30e 2016-05-26 kinaba: #include <iostream> fbe763b30e 2016-05-26 kinaba: #include <sstream> fbe763b30e 2016-05-26 kinaba: #include <iomanip> fbe763b30e 2016-05-26 kinaba: #include <vector> fbe763b30e 2016-05-26 kinaba: #include <string> fbe763b30e 2016-05-26 kinaba: #include <map> fbe763b30e 2016-05-26 kinaba: #include <set> fbe763b30e 2016-05-26 kinaba: #include <algorithm> fbe763b30e 2016-05-26 kinaba: #include <numeric> fbe763b30e 2016-05-26 kinaba: #include <iterator> fbe763b30e 2016-05-26 kinaba: #include <functional> fbe763b30e 2016-05-26 kinaba: #include <complex> fbe763b30e 2016-05-26 kinaba: #include <queue> fbe763b30e 2016-05-26 kinaba: #include <stack> fbe763b30e 2016-05-26 kinaba: #include <cmath> fbe763b30e 2016-05-26 kinaba: #include <cassert> fbe763b30e 2016-05-26 kinaba: #include <tuple> fbe763b30e 2016-05-26 kinaba: using namespace std; fbe763b30e 2016-05-26 kinaba: typedef long long LL; fbe763b30e 2016-05-26 kinaba: typedef complex<double> CMP; fbe763b30e 2016-05-26 kinaba: fbe763b30e 2016-05-26 kinaba: typedef int vert; fbe763b30e 2016-05-26 kinaba: typedef vert edge; fbe763b30e 2016-05-26 kinaba: typedef vector<edge> edges; fbe763b30e 2016-05-26 kinaba: typedef vector<edges> graph; fbe763b30e 2016-05-26 kinaba: fbe763b30e 2016-05-26 kinaba: bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] ) fbe763b30e 2016-05-26 kinaba: { fbe763b30e 2016-05-26 kinaba: for(int i=0; i<G[v].size(); ++i) { fbe763b30e 2016-05-26 kinaba: vert u = G[v][i]; fbe763b30e 2016-05-26 kinaba: if( visited[u] ) continue; fbe763b30e 2016-05-26 kinaba: visited[u] = true; fbe763b30e 2016-05-26 kinaba: fbe763b30e 2016-05-26 kinaba: if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) ) fbe763b30e 2016-05-26 kinaba: { matchTo[v]=u, matchTo[u]=v; return true; } fbe763b30e 2016-05-26 kinaba: } fbe763b30e 2016-05-26 kinaba: return false; fbe763b30e 2016-05-26 kinaba: } fbe763b30e 2016-05-26 kinaba: fbe763b30e 2016-05-26 kinaba: template<int NV> fbe763b30e 2016-05-26 kinaba: int biMatch( graph& G, int L ) // [0,L):left, [L,?):right fbe763b30e 2016-05-26 kinaba: // only left->right edges are used during computation fbe763b30e 2016-05-26 kinaba: { fbe763b30e 2016-05-26 kinaba: vector<vert> matchTo(G.size(), -1); fbe763b30e 2016-05-26 kinaba: int ans = 0; fbe763b30e 2016-05-26 kinaba: for(vert v=0; v<L; ++v) { fbe763b30e 2016-05-26 kinaba: bool visited[NV] = {}; fbe763b30e 2016-05-26 kinaba: if( augment(G, v, matchTo, visited) ) fbe763b30e 2016-05-26 kinaba: ++ans; fbe763b30e 2016-05-26 kinaba: } fbe763b30e 2016-05-26 kinaba: return ans; fbe763b30e 2016-05-26 kinaba: } fbe763b30e 2016-05-26 kinaba: fbe763b30e 2016-05-26 kinaba: class FoxAndGemstone { public: fbe763b30e 2016-05-26 kinaba: string isPossible(vector <string> bags) fbe763b30e 2016-05-26 kinaba: { fbe763b30e 2016-05-26 kinaba: set<char> gems; fbe763b30e 2016-05-26 kinaba: for(auto& bag: bags) fbe763b30e 2016-05-26 kinaba: for(char gem: bag) fbe763b30e 2016-05-26 kinaba: gems.insert(gem); fbe763b30e 2016-05-26 kinaba: fbe763b30e 2016-05-26 kinaba: vector<char> g(gems.begin(), gems.end()); fbe763b30e 2016-05-26 kinaba: do { fbe763b30e 2016-05-26 kinaba: bool ok = false; fbe763b30e 2016-05-26 kinaba: for(int x=0; x<bags.size(); ++x) { fbe763b30e 2016-05-26 kinaba: bool fail = false; fbe763b30e 2016-05-26 kinaba: for(int y=0; y<bags.size(); ++y) if(x!=y) fbe763b30e 2016-05-26 kinaba: if(!surely_heavy(bags[x], bags[y], g)) fbe763b30e 2016-05-26 kinaba: fail=true; fbe763b30e 2016-05-26 kinaba: if(!fail) fbe763b30e 2016-05-26 kinaba: ok = true; fbe763b30e 2016-05-26 kinaba: } fbe763b30e 2016-05-26 kinaba: if(!ok) fbe763b30e 2016-05-26 kinaba: return "Impossible"; fbe763b30e 2016-05-26 kinaba: } while(next_permutation(g.begin(), g.end())); fbe763b30e 2016-05-26 kinaba: return "Possible"; fbe763b30e 2016-05-26 kinaba: } fbe763b30e 2016-05-26 kinaba: fbe763b30e 2016-05-26 kinaba: // w[a] >= w[b] for sure fbe763b30e 2016-05-26 kinaba: bool surely_heavy(const string& a, const string& b, vector<char> g) fbe763b30e 2016-05-26 kinaba: { fbe763b30e 2016-05-26 kinaba: if(a.size() < b.size()) fbe763b30e 2016-05-26 kinaba: return false; fbe763b30e 2016-05-26 kinaba: fbe763b30e 2016-05-26 kinaba: graph G(a.size()+b.size()); fbe763b30e 2016-05-26 kinaba: for(int x=0; x<a.size(); ++x) fbe763b30e 2016-05-26 kinaba: for(int y=0; y<b.size(); ++y) fbe763b30e 2016-05-26 kinaba: if(find(g.begin(),g.end(),a[x]) >= find(g.begin(),g.end(),b[y])) fbe763b30e 2016-05-26 kinaba: G[x].emplace_back(a.size()+y); fbe763b30e 2016-05-26 kinaba: fbe763b30e 2016-05-26 kinaba: return biMatch<100>(G, a.size()) == b.size(); fbe763b30e 2016-05-26 kinaba: } fbe763b30e 2016-05-26 kinaba: }; fbe763b30e 2016-05-26 kinaba: fbe763b30e 2016-05-26 kinaba: // BEGIN CUT HERE fbe763b30e 2016-05-26 kinaba: #include <ctime> fbe763b30e 2016-05-26 kinaba: double start_time; string timer() fbe763b30e 2016-05-26 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } fbe763b30e 2016-05-26 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) fbe763b30e 2016-05-26 kinaba: { os << "{ "; fbe763b30e 2016-05-26 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) fbe763b30e 2016-05-26 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } fbe763b30e 2016-05-26 kinaba: void verify_case(const string& Expected, const string& Received) { fbe763b30e 2016-05-26 kinaba: bool ok = (Expected == Received); fbe763b30e 2016-05-26 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; fbe763b30e 2016-05-26 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } fbe763b30e 2016-05-26 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); fbe763b30e 2016-05-26 kinaba: #define END verify_case(_, FoxAndGemstone().isPossible(bags));} fbe763b30e 2016-05-26 kinaba: int main(){ fbe763b30e 2016-05-26 kinaba: fbe763b30e 2016-05-26 kinaba: CASE(0) fbe763b30e 2016-05-26 kinaba: string bags_[] = {"AB", "AC"}; fbe763b30e 2016-05-26 kinaba: vector <string> bags(bags_, bags_+sizeof(bags_)/sizeof(*bags_)); fbe763b30e 2016-05-26 kinaba: string _ = "Possible"; fbe763b30e 2016-05-26 kinaba: END fbe763b30e 2016-05-26 kinaba: CASE(1) fbe763b30e 2016-05-26 kinaba: string bags_[] = {"A", "BC"}; fbe763b30e 2016-05-26 kinaba: vector <string> bags(bags_, bags_+sizeof(bags_)/sizeof(*bags_)); fbe763b30e 2016-05-26 kinaba: string _ = "Impossible"; fbe763b30e 2016-05-26 kinaba: END fbe763b30e 2016-05-26 kinaba: CASE(2) fbe763b30e 2016-05-26 kinaba: string bags_[] = {"A", "B", "C", "AB", "AC", "BC", "ABC"}; fbe763b30e 2016-05-26 kinaba: vector <string> bags(bags_, bags_+sizeof(bags_)/sizeof(*bags_)); fbe763b30e 2016-05-26 kinaba: string _ = "Possible"; fbe763b30e 2016-05-26 kinaba: END fbe763b30e 2016-05-26 kinaba: CASE(3) fbe763b30e 2016-05-26 kinaba: string bags_[] = {"AB","AC","AD","BC","BD","CD"}; fbe763b30e 2016-05-26 kinaba: vector <string> bags(bags_, bags_+sizeof(bags_)/sizeof(*bags_)); fbe763b30e 2016-05-26 kinaba: string _ = "Possible"; fbe763b30e 2016-05-26 kinaba: END fbe763b30e 2016-05-26 kinaba: CASE(4) fbe763b30e 2016-05-26 kinaba: string bags_[] = {"AB", "CD"}; fbe763b30e 2016-05-26 kinaba: vector <string> bags(bags_, bags_+sizeof(bags_)/sizeof(*bags_)); fbe763b30e 2016-05-26 kinaba: string _ = "Impossible"; fbe763b30e 2016-05-26 kinaba: END fbe763b30e 2016-05-26 kinaba: CASE(5) fbe763b30e 2016-05-26 kinaba: string bags_[] = {"A", "A", "A"}; fbe763b30e 2016-05-26 kinaba: vector <string> bags(bags_, bags_+sizeof(bags_)/sizeof(*bags_)); fbe763b30e 2016-05-26 kinaba: string _ = "Possible"; fbe763b30e 2016-05-26 kinaba: END fbe763b30e 2016-05-26 kinaba: /* fbe763b30e 2016-05-26 kinaba: CASE(6) fbe763b30e 2016-05-26 kinaba: string bags_[] = ; fbe763b30e 2016-05-26 kinaba: vector <string> bags(bags_, bags_+sizeof(bags_)/sizeof(*bags_)); fbe763b30e 2016-05-26 kinaba: string _ = ; fbe763b30e 2016-05-26 kinaba: END fbe763b30e 2016-05-26 kinaba: CASE(7) fbe763b30e 2016-05-26 kinaba: string bags_[] = ; fbe763b30e 2016-05-26 kinaba: vector <string> bags(bags_, bags_+sizeof(bags_)/sizeof(*bags_)); fbe763b30e 2016-05-26 kinaba: string _ = ; fbe763b30e 2016-05-26 kinaba: END fbe763b30e 2016-05-26 kinaba: */ fbe763b30e 2016-05-26 kinaba: } fbe763b30e 2016-05-26 kinaba: // END CUT HERE