4fd800b3a8 2011-02-23 kinaba: #include <iostream> 4fd800b3a8 2011-02-23 kinaba: #include <sstream> 4fd800b3a8 2011-02-23 kinaba: #include <iomanip> 4fd800b3a8 2011-02-23 kinaba: #include <vector> 4fd800b3a8 2011-02-23 kinaba: #include <string> 4fd800b3a8 2011-02-23 kinaba: #include <map> 4fd800b3a8 2011-02-23 kinaba: #include <set> 4fd800b3a8 2011-02-23 kinaba: #include <algorithm> 4fd800b3a8 2011-02-23 kinaba: #include <numeric> 4fd800b3a8 2011-02-23 kinaba: #include <iterator> 4fd800b3a8 2011-02-23 kinaba: #include <functional> 4fd800b3a8 2011-02-23 kinaba: #include <complex> 4fd800b3a8 2011-02-23 kinaba: #include <queue> 4fd800b3a8 2011-02-23 kinaba: #include <stack> 4fd800b3a8 2011-02-23 kinaba: #include <cmath> 4fd800b3a8 2011-02-23 kinaba: #include <cassert> 4fd800b3a8 2011-02-23 kinaba: #include <cstring> 4fd800b3a8 2011-02-23 kinaba: using namespace std; 4fd800b3a8 2011-02-23 kinaba: typedef long long LL; 4fd800b3a8 2011-02-23 kinaba: typedef complex<double> CMP; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: static const int NV = 18*18*2+18+2; 4fd800b3a8 2011-02-23 kinaba: typedef int flow; 4fd800b3a8 2011-02-23 kinaba: typedef LL cost; 4fd800b3a8 2011-02-23 kinaba: typedef int vert; 4fd800b3a8 2011-02-23 kinaba: typedef vert edge; 4fd800b3a8 2011-02-23 kinaba: typedef vector<edge> edges; 4fd800b3a8 2011-02-23 kinaba: typedef vector<edges> graph; 4fd800b3a8 2011-02-23 kinaba: typedef flow flow_graph[NV][NV]; 4fd800b3a8 2011-02-23 kinaba: typedef cost cost_graph[NV][NV]; 4fd800b3a8 2011-02-23 kinaba: static const flow FLOW_INF = 0x7FFFFFFF; 4fd800b3a8 2011-02-23 kinaba: static const cost COST_INF = 0x7FFFFFFFFFFFFFFFLL; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // edges(bidi), capacity, cost(s.t. C[x][y]=-C[y][x]) per 1 flow, src, dst 4fd800b3a8 2011-02-23 kinaba: pair<cost,flow> mincostFlow(graph& G, flow_graph F, cost_graph C, vert S, vert D) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: int N = G.size(); 4fd800b3a8 2011-02-23 kinaba: cost total_cost = 0; 4fd800b3a8 2011-02-23 kinaba: flow total_flow = 0; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: vector<cost> h(N, 0); // potential 4fd800b3a8 2011-02-23 kinaba: for(cost RF=FLOW_INF; RF>0; ) // residual flow 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: // Dijkstra -- find the min-cost path 4fd800b3a8 2011-02-23 kinaba: vector<cost> d(N, COST_INF); d[S] = 0; 4fd800b3a8 2011-02-23 kinaba: vector<vert> prev(N, -1); 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: typedef pair<cost, pair<vert,vert> > cedge; 4fd800b3a8 2011-02-23 kinaba: priority_queue< cedge, vector<cedge>, greater<cedge> > Q; 4fd800b3a8 2011-02-23 kinaba: Q.push( cedge(0, make_pair(S,S)) ); 4fd800b3a8 2011-02-23 kinaba: while( !Q.empty() ) { 4fd800b3a8 2011-02-23 kinaba: cedge e = Q.top(); Q.pop(); 4fd800b3a8 2011-02-23 kinaba: if( prev[e.second.second] >= 0 ) 4fd800b3a8 2011-02-23 kinaba: continue; 4fd800b3a8 2011-02-23 kinaba: prev[e.second.second] = e.second.first; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: vert u = e.second.second; 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<G[u].size(); ++i) { 4fd800b3a8 2011-02-23 kinaba: vert v = G[u][i]; 4fd800b3a8 2011-02-23 kinaba: cost r_cost = C[u][v] + h[u] - h[v]; 4fd800b3a8 2011-02-23 kinaba: if( F[u][v] > 0 && d[v] > d[u]+r_cost ) 4fd800b3a8 2011-02-23 kinaba: Q.push( cedge(d[v]=d[u]+r_cost, make_pair(u,v)) ); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: if( prev[D] < 0 ) 4fd800b3a8 2011-02-23 kinaba: break; // Finished 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // As much as possible 4fd800b3a8 2011-02-23 kinaba: flow f = RF; 4fd800b3a8 2011-02-23 kinaba: for(vert u=D; u!=S; u=prev[u]) 4fd800b3a8 2011-02-23 kinaba: f = min(f, F[prev[u]][u]); 4fd800b3a8 2011-02-23 kinaba: RF -= f; 4fd800b3a8 2011-02-23 kinaba: total_flow += f; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: for(vert u=D; u!=S; u=prev[u]) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: total_cost += f * C[prev[u]][u]; 4fd800b3a8 2011-02-23 kinaba: F[prev[u]][u] -= f; 4fd800b3a8 2011-02-23 kinaba: F[u][prev[u]] += f; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // Update the potential 4fd800b3a8 2011-02-23 kinaba: for(vert u=0; u<N; ++u) 4fd800b3a8 2011-02-23 kinaba: h[u] += d[u]; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: return make_pair(total_cost, total_flow); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: flow_graph F; 4fd800b3a8 2011-02-23 kinaba: cost_graph C; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: LL f(LL n) { 4fd800b3a8 2011-02-23 kinaba: return n*n*n*n*n; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: class TheSquareDivOne { public: 4fd800b3a8 2011-02-23 kinaba: vector <string> solve(vector <string> board) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: int n = board.size(); 4fd800b3a8 2011-02-23 kinaba: vector<int> R(n); 4fd800b3a8 2011-02-23 kinaba: for(int y=0; y<n; ++y) 4fd800b3a8 2011-02-23 kinaba: for(int x=0; x<n; ++x) 4fd800b3a8 2011-02-23 kinaba: if( board[y][x]=='C' ) 4fd800b3a8 2011-02-23 kinaba: R[y] ++; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: graph G(2+n+n*n*2); 4fd800b3a8 2011-02-23 kinaba: memset(F, 0, sizeof(F)); 4fd800b3a8 2011-02-23 kinaba: memset(C, 0, sizeof(C)); 4fd800b3a8 2011-02-23 kinaba: vert S = 0; 4fd800b3a8 2011-02-23 kinaba: vert D = 1; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: for(int y=0; y<n; ++y) 4fd800b3a8 2011-02-23 kinaba: for(int x=0; x<n; ++x) { 4fd800b3a8 2011-02-23 kinaba: vert v = (2+n) + y*n + x; 4fd800b3a8 2011-02-23 kinaba: G[S].push_back(v); 4fd800b3a8 2011-02-23 kinaba: G[v].push_back(S); 4fd800b3a8 2011-02-23 kinaba: if( board[y][x]=='C' ) 4fd800b3a8 2011-02-23 kinaba: F[S][v] = 1; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: for(int y=0; y<n; ++y) 4fd800b3a8 2011-02-23 kinaba: for(int x=0; x<n; ++x) { 4fd800b3a8 2011-02-23 kinaba: vert v = (2+n) + (n*n) + y*n + x; 4fd800b3a8 2011-02-23 kinaba: vert u = 2+x; 4fd800b3a8 2011-02-23 kinaba: G[v].push_back(u); 4fd800b3a8 2011-02-23 kinaba: G[u].push_back(v); 4fd800b3a8 2011-02-23 kinaba: F[v][u] = 1; 4fd800b3a8 2011-02-23 kinaba: // C[u][v] = -(C[v][u] = (1LL<<(n-y-1))<<30); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: for(int x=0; x<n; ++x) { 4fd800b3a8 2011-02-23 kinaba: vert u = 2+x; 4fd800b3a8 2011-02-23 kinaba: G[u].push_back(D); 4fd800b3a8 2011-02-23 kinaba: G[D].push_back(u); 4fd800b3a8 2011-02-23 kinaba: F[u][D] = R[x]; 4fd800b3a8 2011-02-23 kinaba: // C[u][D] = -(C[D][u] = (1LL<<2*(n-x-1))); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: for(int y1=0; y1<n; ++y1) 4fd800b3a8 2011-02-23 kinaba: for(int x1=0; x1<n; ++x1) 4fd800b3a8 2011-02-23 kinaba: for(int y2=0; y2<n; ++y2) 4fd800b3a8 2011-02-23 kinaba: for(int x2=0; x2<n; ++x2) { 4fd800b3a8 2011-02-23 kinaba: vert v = (2+n) + y1*n + x1; 4fd800b3a8 2011-02-23 kinaba: vert u = (2+n) + (n*n) + y2*n + x2; 4fd800b3a8 2011-02-23 kinaba: G[u].push_back(v); 4fd800b3a8 2011-02-23 kinaba: G[v].push_back(u); 4fd800b3a8 2011-02-23 kinaba: F[v][u] = 1; 4fd800b3a8 2011-02-23 kinaba: C[u][v] = -(C[v][u] = abs(y1-y2)+abs(x1-x2)); 4fd800b3a8 2011-02-23 kinaba: // C[u][v] = -(C[v][u] = LL(abs(y1-y2)+abs(x1-x2))<<50); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: pair<cost,flow> mf = mincostFlow(G,F,C,S,D); 4fd800b3a8 2011-02-23 kinaba: // cerr << "Cost: " << (mf.first>>50) << "+" << ((mf.first&(1LL<<50)-1)) << ", Flow: " << mf.second << endl; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: for(int y=0; y<n; ++y) 4fd800b3a8 2011-02-23 kinaba: for(int x=0; x<n; ++x) 4fd800b3a8 2011-02-23 kinaba: board[y][x] = (F[(2+n) + (n*n) + y*n + x][2+x]==0 ? 'C' : '.'); 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // not lexicographically first ...orz 4fd800b3a8 2011-02-23 kinaba: return board; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: }; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // BEGIN CUT HERE 4fd800b3a8 2011-02-23 kinaba: #include <ctime> 4fd800b3a8 2011-02-23 kinaba: double start_time; string timer() 4fd800b3a8 2011-02-23 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 4fd800b3a8 2011-02-23 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 4fd800b3a8 2011-02-23 kinaba: { os << "{ "; 4fd800b3a8 2011-02-23 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 4fd800b3a8 2011-02-23 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 4fd800b3a8 2011-02-23 kinaba: void verify_case(const vector <string>& Expected, const vector <string>& Received) { 4fd800b3a8 2011-02-23 kinaba: bool ok = (Expected == Received); 4fd800b3a8 2011-02-23 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 4fd800b3a8 2011-02-23 kinaba: cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } 4fd800b3a8 2011-02-23 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 4fd800b3a8 2011-02-23 kinaba: #define END verify_case(_, TheSquareDivOne().solve(board));} 4fd800b3a8 2011-02-23 kinaba: int main(){ 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: CASE(0) 4fd800b3a8 2011-02-23 kinaba: string board_[] = {"...", 4fd800b3a8 2011-02-23 kinaba: "...", 4fd800b3a8 2011-02-23 kinaba: "C.."}; 4fd800b3a8 2011-02-23 kinaba: vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 4fd800b3a8 2011-02-23 kinaba: string __[] = {"...", "...", "..C" }; 4fd800b3a8 2011-02-23 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(1) 4fd800b3a8 2011-02-23 kinaba: string board_[] = {"CCC", 4fd800b3a8 2011-02-23 kinaba: ".C.", 4fd800b3a8 2011-02-23 kinaba: "CCC"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 4fd800b3a8 2011-02-23 kinaba: string __[] = {"C.C", "C.C", "CCC" }; 4fd800b3a8 2011-02-23 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(2) 4fd800b3a8 2011-02-23 kinaba: string board_[] = {"C..", 4fd800b3a8 2011-02-23 kinaba: ".C.", 4fd800b3a8 2011-02-23 kinaba: "..C"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 4fd800b3a8 2011-02-23 kinaba: string __[] = {"C..", ".C.", "..C" }; 4fd800b3a8 2011-02-23 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(3) 4fd800b3a8 2011-02-23 kinaba: string board_[] = {"C....","CCCCC","...CC",".CC..",".C.C."}; 4fd800b3a8 2011-02-23 kinaba: vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 4fd800b3a8 2011-02-23 kinaba: string __[] = {".C...", "CCCCC", ".C..C", ".CC..", ".C.C." }; 4fd800b3a8 2011-02-23 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(4) 4fd800b3a8 2011-02-23 kinaba: string board_[] = { 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: }; 4fd800b3a8 2011-02-23 kinaba: vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 4fd800b3a8 2011-02-23 kinaba: string __[] = { 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: "CCCCCCCCCCCCCCCCCC", 4fd800b3a8 2011-02-23 kinaba: }; 4fd800b3a8 2011-02-23 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: /* 4fd800b3a8 2011-02-23 kinaba: CASE(5) 4fd800b3a8 2011-02-23 kinaba: string board_[] = ; 4fd800b3a8 2011-02-23 kinaba: vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 4fd800b3a8 2011-02-23 kinaba: string __[] = ; 4fd800b3a8 2011-02-23 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: */ 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: // END CUT HERE