aca31be9a5 2011-12-24 kinaba: #include <iostream> aca31be9a5 2011-12-24 kinaba: #include <sstream> aca31be9a5 2011-12-24 kinaba: #include <iomanip> aca31be9a5 2011-12-24 kinaba: #include <vector> aca31be9a5 2011-12-24 kinaba: #include <string> aca31be9a5 2011-12-24 kinaba: #include <map> aca31be9a5 2011-12-24 kinaba: #include <set> aca31be9a5 2011-12-24 kinaba: #include <algorithm> aca31be9a5 2011-12-24 kinaba: #include <numeric> aca31be9a5 2011-12-24 kinaba: #include <iterator> aca31be9a5 2011-12-24 kinaba: #include <functional> aca31be9a5 2011-12-24 kinaba: #include <complex> aca31be9a5 2011-12-24 kinaba: #include <queue> aca31be9a5 2011-12-24 kinaba: #include <stack> aca31be9a5 2011-12-24 kinaba: #include <cmath> aca31be9a5 2011-12-24 kinaba: #include <cassert> aca31be9a5 2011-12-24 kinaba: #include <cstring> aca31be9a5 2011-12-24 kinaba: #ifdef __GNUC__ aca31be9a5 2011-12-24 kinaba: #include <ext/hash_map> aca31be9a5 2011-12-24 kinaba: #define unordered_map __gnu_cxx::hash_map aca31be9a5 2011-12-24 kinaba: #else aca31be9a5 2011-12-24 kinaba: #include <unordered_map> aca31be9a5 2011-12-24 kinaba: #endif aca31be9a5 2011-12-24 kinaba: using namespace std; aca31be9a5 2011-12-24 kinaba: typedef long long LL; aca31be9a5 2011-12-24 kinaba: typedef complex<double> CMP; aca31be9a5 2011-12-24 kinaba: aca31be9a5 2011-12-24 kinaba: typedef int vert; aca31be9a5 2011-12-24 kinaba: typedef vert edge; aca31be9a5 2011-12-24 kinaba: typedef vector<edge> edges; aca31be9a5 2011-12-24 kinaba: typedef vector<edges> graph; aca31be9a5 2011-12-24 kinaba: aca31be9a5 2011-12-24 kinaba: bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] ) aca31be9a5 2011-12-24 kinaba: { aca31be9a5 2011-12-24 kinaba: for(int i=0; i<G[v].size(); ++i) { aca31be9a5 2011-12-24 kinaba: vert u = G[v][i]; aca31be9a5 2011-12-24 kinaba: if( visited[u] ) continue; aca31be9a5 2011-12-24 kinaba: visited[u] = true; aca31be9a5 2011-12-24 kinaba: aca31be9a5 2011-12-24 kinaba: if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) ) aca31be9a5 2011-12-24 kinaba: { matchTo[v]=u, matchTo[u]=v; return true; } aca31be9a5 2011-12-24 kinaba: } aca31be9a5 2011-12-24 kinaba: return false; aca31be9a5 2011-12-24 kinaba: } aca31be9a5 2011-12-24 kinaba: aca31be9a5 2011-12-24 kinaba: template<int NV> aca31be9a5 2011-12-24 kinaba: int biMatch( graph& G, int L ) // [0,L):left, [L,?):right aca31be9a5 2011-12-24 kinaba: // only left->right edges are used during computation aca31be9a5 2011-12-24 kinaba: { aca31be9a5 2011-12-24 kinaba: vector<vert> matchTo(G.size(), -1); aca31be9a5 2011-12-24 kinaba: int ans = 0; aca31be9a5 2011-12-24 kinaba: for(vert v=0; v<L; ++v) { aca31be9a5 2011-12-24 kinaba: bool visited[NV] = {}; aca31be9a5 2011-12-24 kinaba: if( augment(G, v, matchTo, visited) ) aca31be9a5 2011-12-24 kinaba: ++ans; aca31be9a5 2011-12-24 kinaba: } aca31be9a5 2011-12-24 kinaba: return ans; aca31be9a5 2011-12-24 kinaba: } aca31be9a5 2011-12-24 kinaba: aca31be9a5 2011-12-24 kinaba: class P8XMatrixRecovery { public: aca31be9a5 2011-12-24 kinaba: int H, W; aca31be9a5 2011-12-24 kinaba: vector <string> solve(vector <string> rows, vector <string> columns) aca31be9a5 2011-12-24 kinaba: { aca31be9a5 2011-12-24 kinaba: H = rows.size(); aca31be9a5 2011-12-24 kinaba: W = rows[0].size(); aca31be9a5 2011-12-24 kinaba: for(int y=0; y<H; ++y) aca31be9a5 2011-12-24 kinaba: for(int x=0; x<W; ++x) aca31be9a5 2011-12-24 kinaba: if( rows[y][x] == '?' ) { aca31be9a5 2011-12-24 kinaba: rows[y][x] = '0'; aca31be9a5 2011-12-24 kinaba: if( !can(rows, columns) ) aca31be9a5 2011-12-24 kinaba: rows[y][x] = '1'; aca31be9a5 2011-12-24 kinaba: } aca31be9a5 2011-12-24 kinaba: return rows; aca31be9a5 2011-12-24 kinaba: } aca31be9a5 2011-12-24 kinaba: aca31be9a5 2011-12-24 kinaba: bool can(const vector<string>& rows, const vector<string>& columns) aca31be9a5 2011-12-24 kinaba: { aca31be9a5 2011-12-24 kinaba: graph G(W*2); aca31be9a5 2011-12-24 kinaba: for(int x1=0; x1<W; ++x1) { aca31be9a5 2011-12-24 kinaba: string left; aca31be9a5 2011-12-24 kinaba: for(int y=0; y<H; ++y) aca31be9a5 2011-12-24 kinaba: left += rows[y][x1]; aca31be9a5 2011-12-24 kinaba: for(int x2=0; x2<W; ++x2) aca31be9a5 2011-12-24 kinaba: if( match(left, columns[x2]) ) aca31be9a5 2011-12-24 kinaba: G[x1].push_back(x2+W); aca31be9a5 2011-12-24 kinaba: } aca31be9a5 2011-12-24 kinaba: return biMatch<60>(G, W) == W; aca31be9a5 2011-12-24 kinaba: } aca31be9a5 2011-12-24 kinaba: aca31be9a5 2011-12-24 kinaba: bool match( const string& l, const string& r ) aca31be9a5 2011-12-24 kinaba: { aca31be9a5 2011-12-24 kinaba: for(int i=0; i<l.size(); ++i) aca31be9a5 2011-12-24 kinaba: if( l[i]!=r[i] && l[i]!='?' && r[i]!='?' ) aca31be9a5 2011-12-24 kinaba: return false; aca31be9a5 2011-12-24 kinaba: return true; aca31be9a5 2011-12-24 kinaba: } aca31be9a5 2011-12-24 kinaba: }; aca31be9a5 2011-12-24 kinaba: aca31be9a5 2011-12-24 kinaba: // BEGIN CUT HERE aca31be9a5 2011-12-24 kinaba: #include <ctime> aca31be9a5 2011-12-24 kinaba: double start_time; string timer() aca31be9a5 2011-12-24 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } aca31be9a5 2011-12-24 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) aca31be9a5 2011-12-24 kinaba: { os << "{ "; aca31be9a5 2011-12-24 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) aca31be9a5 2011-12-24 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } aca31be9a5 2011-12-24 kinaba: void verify_case(const vector <string>& Expected, const vector <string>& Received) { aca31be9a5 2011-12-24 kinaba: bool ok = (Expected == Received); aca31be9a5 2011-12-24 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; aca31be9a5 2011-12-24 kinaba: cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } aca31be9a5 2011-12-24 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); aca31be9a5 2011-12-24 kinaba: #define END verify_case(_, P8XMatrixRecovery().solve(rows, columns));} aca31be9a5 2011-12-24 kinaba: int main(){ aca31be9a5 2011-12-24 kinaba: aca31be9a5 2011-12-24 kinaba: CASE(0) aca31be9a5 2011-12-24 kinaba: string rows_[] = {"10?" aca31be9a5 2011-12-24 kinaba: ,"?11"}; aca31be9a5 2011-12-24 kinaba: vector <string> rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_)); aca31be9a5 2011-12-24 kinaba: string columns_[] = {"01" aca31be9a5 2011-12-24 kinaba: ,"10" aca31be9a5 2011-12-24 kinaba: ,"1?"} aca31be9a5 2011-12-24 kinaba: ; aca31be9a5 2011-12-24 kinaba: vector <string> columns(columns_, columns_+sizeof(columns_)/sizeof(*columns_)); aca31be9a5 2011-12-24 kinaba: string __[] = {"101", "011" }; aca31be9a5 2011-12-24 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); aca31be9a5 2011-12-24 kinaba: END aca31be9a5 2011-12-24 kinaba: CASE(1) aca31be9a5 2011-12-24 kinaba: string rows_[] = {"0" aca31be9a5 2011-12-24 kinaba: ,"?" aca31be9a5 2011-12-24 kinaba: ,"1"}; aca31be9a5 2011-12-24 kinaba: vector <string> rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_)); aca31be9a5 2011-12-24 kinaba: string columns_[] = {"0?1"}; aca31be9a5 2011-12-24 kinaba: vector <string> columns(columns_, columns_+sizeof(columns_)/sizeof(*columns_)); aca31be9a5 2011-12-24 kinaba: string __[] = {"0", "0", "1" }; aca31be9a5 2011-12-24 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); aca31be9a5 2011-12-24 kinaba: END aca31be9a5 2011-12-24 kinaba: CASE(2) aca31be9a5 2011-12-24 kinaba: string rows_[] = {"10" aca31be9a5 2011-12-24 kinaba: ,"01"}; aca31be9a5 2011-12-24 kinaba: vector <string> rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_)); aca31be9a5 2011-12-24 kinaba: string columns_[] = {"10" aca31be9a5 2011-12-24 kinaba: ,"01"}; aca31be9a5 2011-12-24 kinaba: vector <string> columns(columns_, columns_+sizeof(columns_)/sizeof(*columns_)); aca31be9a5 2011-12-24 kinaba: string __[] = {"10", "01" }; aca31be9a5 2011-12-24 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); aca31be9a5 2011-12-24 kinaba: END aca31be9a5 2011-12-24 kinaba: CASE(3) aca31be9a5 2011-12-24 kinaba: string rows_[] = {"??0" aca31be9a5 2011-12-24 kinaba: ,"11?" aca31be9a5 2011-12-24 kinaba: ,"?01" aca31be9a5 2011-12-24 kinaba: ,"1?1"}; aca31be9a5 2011-12-24 kinaba: vector <string> rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_)); aca31be9a5 2011-12-24 kinaba: string columns_[] = {"1???" aca31be9a5 2011-12-24 kinaba: ,"?111" aca31be9a5 2011-12-24 kinaba: ,"0?1?"}; aca31be9a5 2011-12-24 kinaba: vector <string> columns(columns_, columns_+sizeof(columns_)/sizeof(*columns_)); aca31be9a5 2011-12-24 kinaba: string __[] = {"010", "110", "101", "101" }; aca31be9a5 2011-12-24 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); aca31be9a5 2011-12-24 kinaba: END aca31be9a5 2011-12-24 kinaba: CASE(4) aca31be9a5 2011-12-24 kinaba: string rows_[] = { aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: }; aca31be9a5 2011-12-24 kinaba: vector <string> rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_)); aca31be9a5 2011-12-24 kinaba: string columns_[] = { aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: "??????????????????????????????", aca31be9a5 2011-12-24 kinaba: }; aca31be9a5 2011-12-24 kinaba: vector <string> columns(columns_, columns_+sizeof(columns_)/sizeof(*columns_)); aca31be9a5 2011-12-24 kinaba: string __[] = {"?"}; aca31be9a5 2011-12-24 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); aca31be9a5 2011-12-24 kinaba: END aca31be9a5 2011-12-24 kinaba: CASE(5) aca31be9a5 2011-12-24 kinaba: string rows_[] = {"?"}; aca31be9a5 2011-12-24 kinaba: vector <string> rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_)); aca31be9a5 2011-12-24 kinaba: string columns_[] = {"?"}; aca31be9a5 2011-12-24 kinaba: vector <string> columns(columns_, columns_+sizeof(columns_)/sizeof(*columns_)); aca31be9a5 2011-12-24 kinaba: string __[] = {"0"}; aca31be9a5 2011-12-24 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); aca31be9a5 2011-12-24 kinaba: END aca31be9a5 2011-12-24 kinaba: CASE(6) aca31be9a5 2011-12-24 kinaba: string rows_[] = {"??","??"}; aca31be9a5 2011-12-24 kinaba: vector <string> rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_)); aca31be9a5 2011-12-24 kinaba: string columns_[] = {"00","11"}; aca31be9a5 2011-12-24 kinaba: vector <string> columns(columns_, columns_+sizeof(columns_)/sizeof(*columns_)); aca31be9a5 2011-12-24 kinaba: string __[] = {"01","01"}; aca31be9a5 2011-12-24 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); aca31be9a5 2011-12-24 kinaba: END aca31be9a5 2011-12-24 kinaba: CASE(7) aca31be9a5 2011-12-24 kinaba: string rows_[] = {"0??", "?0?"}; aca31be9a5 2011-12-24 kinaba: vector <string> rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_)); aca31be9a5 2011-12-24 kinaba: string columns_[] = {"01", "00", "10"}; aca31be9a5 2011-12-24 kinaba: vector <string> columns(columns_, columns_+sizeof(columns_)/sizeof(*columns_)); aca31be9a5 2011-12-24 kinaba: string __[] = {"001", "100"}; aca31be9a5 2011-12-24 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); aca31be9a5 2011-12-24 kinaba: END aca31be9a5 2011-12-24 kinaba: aca31be9a5 2011-12-24 kinaba: } aca31be9a5 2011-12-24 kinaba: // END CUT HERE