5b7cb6883d 2015-09-28 kinaba: #include <iostream> 5b7cb6883d 2015-09-28 kinaba: #include <sstream> 5b7cb6883d 2015-09-28 kinaba: #include <iomanip> 5b7cb6883d 2015-09-28 kinaba: #include <vector> 5b7cb6883d 2015-09-28 kinaba: #include <string> 5b7cb6883d 2015-09-28 kinaba: #include <map> 5b7cb6883d 2015-09-28 kinaba: #include <set> 5b7cb6883d 2015-09-28 kinaba: #include <algorithm> 5b7cb6883d 2015-09-28 kinaba: #include <numeric> 5b7cb6883d 2015-09-28 kinaba: #include <iterator> 5b7cb6883d 2015-09-28 kinaba: #include <functional> 5b7cb6883d 2015-09-28 kinaba: #include <complex> 5b7cb6883d 2015-09-28 kinaba: #include <queue> 5b7cb6883d 2015-09-28 kinaba: #include <stack> 5b7cb6883d 2015-09-28 kinaba: #include <cmath> 5b7cb6883d 2015-09-28 kinaba: #include <cassert> 5b7cb6883d 2015-09-28 kinaba: #include <tuple> 5b7cb6883d 2015-09-28 kinaba: using namespace std; 5b7cb6883d 2015-09-28 kinaba: typedef long long LL; 5b7cb6883d 2015-09-28 kinaba: typedef complex<double> CMP; 5b7cb6883d 2015-09-28 kinaba: 5b7cb6883d 2015-09-28 kinaba: inline int bitcnt(int x) 5b7cb6883d 2015-09-28 kinaba: { 5b7cb6883d 2015-09-28 kinaba: int c = 0; 5b7cb6883d 2015-09-28 kinaba: for(; x; x>>=1) 5b7cb6883d 2015-09-28 kinaba: c += x&1; 5b7cb6883d 2015-09-28 kinaba: return c; 5b7cb6883d 2015-09-28 kinaba: } 5b7cb6883d 2015-09-28 kinaba: 5b7cb6883d 2015-09-28 kinaba: class OrderOfOperations { public: 5b7cb6883d 2015-09-28 kinaba: int minTime(vector <string> s) 5b7cb6883d 2015-09-28 kinaba: { 5b7cb6883d 2015-09-28 kinaba: const int M = s[0].size(); 5b7cb6883d 2015-09-28 kinaba: 5b7cb6883d 2015-09-28 kinaba: vector<int> edge; 5b7cb6883d 2015-09-28 kinaba: int all = 0; 5b7cb6883d 2015-09-28 kinaba: for(auto& si: s) { 5b7cb6883d 2015-09-28 kinaba: int x = 0; 5b7cb6883d 2015-09-28 kinaba: for(int i=0; i<M; ++i) 5b7cb6883d 2015-09-28 kinaba: x |= (si[i]=='1')<<i; 5b7cb6883d 2015-09-28 kinaba: edge.emplace_back(x); 5b7cb6883d 2015-09-28 kinaba: all |= x; 5b7cb6883d 2015-09-28 kinaba: } 5b7cb6883d 2015-09-28 kinaba: vector<int> nbits; 5b7cb6883d 2015-09-28 kinaba: for(int m=0; m<(1<<M); ++m) 5b7cb6883d 2015-09-28 kinaba: nbits.emplace_back(bitcnt(m)); 5b7cb6883d 2015-09-28 kinaba: 5b7cb6883d 2015-09-28 kinaba: typedef int Vert, Cost; 5b7cb6883d 2015-09-28 kinaba: typedef pair<Cost,Vert> Edge; 5b7cb6883d 2015-09-28 kinaba: priority_queue<Edge, vector<Edge>, greater<Edge>> Q; 5b7cb6883d 2015-09-28 kinaba: Q.emplace(0, 0); 5b7cb6883d 2015-09-28 kinaba: vector<bool> V(1<<M); 5b7cb6883d 2015-09-28 kinaba: while(!Q.empty()) 5b7cb6883d 2015-09-28 kinaba: { 5b7cb6883d 2015-09-28 kinaba: Vert v = Q.top().second; 5b7cb6883d 2015-09-28 kinaba: Cost c = Q.top().first; 5b7cb6883d 2015-09-28 kinaba: Q.pop(); 5b7cb6883d 2015-09-28 kinaba: if( V[v] ) 5b7cb6883d 2015-09-28 kinaba: continue; 5b7cb6883d 2015-09-28 kinaba: V[v] = true; 5b7cb6883d 2015-09-28 kinaba: 5b7cb6883d 2015-09-28 kinaba: if( v == all ) 5b7cb6883d 2015-09-28 kinaba: return c; 5b7cb6883d 2015-09-28 kinaba: 5b7cb6883d 2015-09-28 kinaba: for(auto e: edge) 5b7cb6883d 2015-09-28 kinaba: if( !V[v|e] ) 5b7cb6883d 2015-09-28 kinaba: Q.emplace(c+nbits[(v|e)&~v]*nbits[(v|e)&~v], v|e); 5b7cb6883d 2015-09-28 kinaba: } 5b7cb6883d 2015-09-28 kinaba: return -1; 5b7cb6883d 2015-09-28 kinaba: } 5b7cb6883d 2015-09-28 kinaba: }; 5b7cb6883d 2015-09-28 kinaba: 5b7cb6883d 2015-09-28 kinaba: // BEGIN CUT HERE 5b7cb6883d 2015-09-28 kinaba: #include <ctime> 5b7cb6883d 2015-09-28 kinaba: double start_time; string timer() 5b7cb6883d 2015-09-28 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 5b7cb6883d 2015-09-28 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 5b7cb6883d 2015-09-28 kinaba: { os << "{ "; 5b7cb6883d 2015-09-28 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 5b7cb6883d 2015-09-28 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 5b7cb6883d 2015-09-28 kinaba: void verify_case(const int& Expected, const int& Received) { 5b7cb6883d 2015-09-28 kinaba: bool ok = (Expected == Received); 5b7cb6883d 2015-09-28 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 5b7cb6883d 2015-09-28 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 5b7cb6883d 2015-09-28 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 5b7cb6883d 2015-09-28 kinaba: #define END verify_case(_, OrderOfOperations().minTime(s));} 5b7cb6883d 2015-09-28 kinaba: int main(){ 5b7cb6883d 2015-09-28 kinaba: 5b7cb6883d 2015-09-28 kinaba: CASE(0) 5b7cb6883d 2015-09-28 kinaba: string s_[] = { 5b7cb6883d 2015-09-28 kinaba: "111", 5b7cb6883d 2015-09-28 kinaba: "001", 5b7cb6883d 2015-09-28 kinaba: "010" 5b7cb6883d 2015-09-28 kinaba: }; 5b7cb6883d 2015-09-28 kinaba: vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); 5b7cb6883d 2015-09-28 kinaba: int _ = 3; 5b7cb6883d 2015-09-28 kinaba: END 5b7cb6883d 2015-09-28 kinaba: CASE(1) 5b7cb6883d 2015-09-28 kinaba: string s_[] = { 5b7cb6883d 2015-09-28 kinaba: "11101", 5b7cb6883d 2015-09-28 kinaba: "00111", 5b7cb6883d 2015-09-28 kinaba: "10101", 5b7cb6883d 2015-09-28 kinaba: "00000", 5b7cb6883d 2015-09-28 kinaba: "11000" 5b7cb6883d 2015-09-28 kinaba: }; 5b7cb6883d 2015-09-28 kinaba: vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); 5b7cb6883d 2015-09-28 kinaba: int _ = 9; 5b7cb6883d 2015-09-28 kinaba: END 5b7cb6883d 2015-09-28 kinaba: CASE(2) 5b7cb6883d 2015-09-28 kinaba: string s_[] = { 5b7cb6883d 2015-09-28 kinaba: "11111111111111111111" 5b7cb6883d 2015-09-28 kinaba: }; 5b7cb6883d 2015-09-28 kinaba: vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); 5b7cb6883d 2015-09-28 kinaba: int _ = 400; 5b7cb6883d 2015-09-28 kinaba: END 5b7cb6883d 2015-09-28 kinaba: CASE(3) 5b7cb6883d 2015-09-28 kinaba: string s_[] = { 5b7cb6883d 2015-09-28 kinaba: "1000", 5b7cb6883d 2015-09-28 kinaba: "1100", 5b7cb6883d 2015-09-28 kinaba: "1110" 5b7cb6883d 2015-09-28 kinaba: }; 5b7cb6883d 2015-09-28 kinaba: vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); 5b7cb6883d 2015-09-28 kinaba: int _ = 3; 5b7cb6883d 2015-09-28 kinaba: END 5b7cb6883d 2015-09-28 kinaba: CASE(4) 5b7cb6883d 2015-09-28 kinaba: string s_[] = { 5b7cb6883d 2015-09-28 kinaba: "111", 5b7cb6883d 2015-09-28 kinaba: "111", 5b7cb6883d 2015-09-28 kinaba: "110", 5b7cb6883d 2015-09-28 kinaba: "100" 5b7cb6883d 2015-09-28 kinaba: }; 5b7cb6883d 2015-09-28 kinaba: vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); 5b7cb6883d 2015-09-28 kinaba: int _ = 3; 5b7cb6883d 2015-09-28 kinaba: END 5b7cb6883d 2015-09-28 kinaba: CASE(5) 5b7cb6883d 2015-09-28 kinaba: string s_[] = {"00100001010101000101","11011001110001000111","01011001010101111001","01011100110111000111","11000100001100001000","11110000101111111111","10010110010000000111","10001100001101110001","00010001100000010010","10001111001101101011","01010111000111100110","00111100010101100010","00110111000100111111","01100000110001000010","11011001011011101100","11111101100111101100","10011101010111101010","11001100000100011100","10111010000011100101","11001000000000011110","10110010101111110000","10101001011011100010","00101001111000110100","10011000010100011000","00011000001011110111","00111000101010001111","01011110110001111100","01010001100001010100","11001010000011000101","00000100010101101000","11100110101101011101","01110100101010100011","10100000100100010100","00111101010111101100","10101011110111111011","01001101010110000000","00111110001011010101","01011011010100011111","11011110011011111111","11111100000011110111","00110001010001100010","00100101011011100001","10101111001101011011","01011101100100010010","01000001010011101100","11001010100110001110","00010110001001110001","01000001111111110100","01001100101111101011","00010101001100110110"}; 5b7cb6883d 2015-09-28 kinaba: vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); 5b7cb6883d 2015-09-28 kinaba: int _ = -2; 5b7cb6883d 2015-09-28 kinaba: END 5b7cb6883d 2015-09-28 kinaba: CASE(6) 5b7cb6883d 2015-09-28 kinaba: string s_[] = { 5b7cb6883d 2015-09-28 kinaba: "1100", 5b7cb6883d 2015-09-28 kinaba: "0011", 5b7cb6883d 2015-09-28 kinaba: "0110", 5b7cb6883d 2015-09-28 kinaba: }; 5b7cb6883d 2015-09-28 kinaba: vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); 5b7cb6883d 2015-09-28 kinaba: int _ = 6; 5b7cb6883d 2015-09-28 kinaba: END 5b7cb6883d 2015-09-28 kinaba: } 5b7cb6883d 2015-09-28 kinaba: // END CUT HERE