fa7992ffc5 2012-08-06 kinaba: #include <iostream> fa7992ffc5 2012-08-06 kinaba: #include <sstream> fa7992ffc5 2012-08-06 kinaba: #include <iomanip> fa7992ffc5 2012-08-06 kinaba: #include <vector> fa7992ffc5 2012-08-06 kinaba: #include <string> fa7992ffc5 2012-08-06 kinaba: #include <map> fa7992ffc5 2012-08-06 kinaba: #include <set> fa7992ffc5 2012-08-06 kinaba: #include <algorithm> fa7992ffc5 2012-08-06 kinaba: #include <numeric> fa7992ffc5 2012-08-06 kinaba: #include <iterator> fa7992ffc5 2012-08-06 kinaba: #include <functional> fa7992ffc5 2012-08-06 kinaba: #include <complex> fa7992ffc5 2012-08-06 kinaba: #include <queue> fa7992ffc5 2012-08-06 kinaba: #include <stack> fa7992ffc5 2012-08-06 kinaba: #include <cmath> fa7992ffc5 2012-08-06 kinaba: #include <cassert> fa7992ffc5 2012-08-06 kinaba: using namespace std; fa7992ffc5 2012-08-06 kinaba: typedef long long LL; fa7992ffc5 2012-08-06 kinaba: typedef long double LD; fa7992ffc5 2012-08-06 kinaba: typedef complex<LD> CMP; fa7992ffc5 2012-08-06 kinaba: fa7992ffc5 2012-08-06 kinaba: class RotatingBot { public: fa7992ffc5 2012-08-06 kinaba: int minArea(vector <int> moves) fa7992ffc5 2012-08-06 kinaba: { fa7992ffc5 2012-08-06 kinaba: if( moves.size() == 1 ) { fa7992ffc5 2012-08-06 kinaba: int w = moves[0]+1; fa7992ffc5 2012-08-06 kinaba: return w; fa7992ffc5 2012-08-06 kinaba: } fa7992ffc5 2012-08-06 kinaba: if( moves.size() == 2 ) { fa7992ffc5 2012-08-06 kinaba: int w = moves[0]+1; fa7992ffc5 2012-08-06 kinaba: int h = moves[1]+1; fa7992ffc5 2012-08-06 kinaba: return w*h; fa7992ffc5 2012-08-06 kinaba: } fa7992ffc5 2012-08-06 kinaba: if( moves.size() == 3 ) { fa7992ffc5 2012-08-06 kinaba: int w1 = moves[0]+1; fa7992ffc5 2012-08-06 kinaba: int h = moves[1]+1; fa7992ffc5 2012-08-06 kinaba: int w2 = moves[2]+1; fa7992ffc5 2012-08-06 kinaba: return max(w1,w2)*h; fa7992ffc5 2012-08-06 kinaba: } fa7992ffc5 2012-08-06 kinaba: if( moves.size() == 4 ) { fa7992ffc5 2012-08-06 kinaba: int w1 = moves[0]+1; fa7992ffc5 2012-08-06 kinaba: int h1 = moves[1]+1; fa7992ffc5 2012-08-06 kinaba: int w2 = moves[2]+1; fa7992ffc5 2012-08-06 kinaba: int h2 = moves[3]+1; fa7992ffc5 2012-08-06 kinaba: if( w1 > w2 ) fa7992ffc5 2012-08-06 kinaba: return -1; fa7992ffc5 2012-08-06 kinaba: if( w1 == w2 ) { fa7992ffc5 2012-08-06 kinaba: if( h1 <= h2 ) fa7992ffc5 2012-08-06 kinaba: return -1; fa7992ffc5 2012-08-06 kinaba: else fa7992ffc5 2012-08-06 kinaba: return w1*h1; fa7992ffc5 2012-08-06 kinaba: } fa7992ffc5 2012-08-06 kinaba: return w2*max(h1,h2); fa7992ffc5 2012-08-06 kinaba: } fa7992ffc5 2012-08-06 kinaba: fa7992ffc5 2012-08-06 kinaba: int w1 = moves[0]+1; fa7992ffc5 2012-08-06 kinaba: int h1 = moves[1]+1; fa7992ffc5 2012-08-06 kinaba: int w2 = moves[2]+1; fa7992ffc5 2012-08-06 kinaba: int h2 = moves[3]+1; fa7992ffc5 2012-08-06 kinaba: if( w1 > w2 ) fa7992ffc5 2012-08-06 kinaba: return -1; fa7992ffc5 2012-08-06 kinaba: if( w1 == w2 ) { fa7992ffc5 2012-08-06 kinaba: vector<int> rm = simulate(w1, h1, 0, 0); fa7992ffc5 2012-08-06 kinaba: if( match(rm, moves) ) fa7992ffc5 2012-08-06 kinaba: return w1*h1; fa7992ffc5 2012-08-06 kinaba: else fa7992ffc5 2012-08-06 kinaba: return -1; fa7992ffc5 2012-08-06 kinaba: } else { fa7992ffc5 2012-08-06 kinaba: if( h2<h1 ) fa7992ffc5 2012-08-06 kinaba: return -1; fa7992ffc5 2012-08-06 kinaba: vector<int> rm = simulate(w2, h2, w2-w1, h2-h1); fa7992ffc5 2012-08-06 kinaba: if( match(rm, moves) ) fa7992ffc5 2012-08-06 kinaba: return w2*h2; fa7992ffc5 2012-08-06 kinaba: else fa7992ffc5 2012-08-06 kinaba: return -1; fa7992ffc5 2012-08-06 kinaba: } fa7992ffc5 2012-08-06 kinaba: } fa7992ffc5 2012-08-06 kinaba: fa7992ffc5 2012-08-06 kinaba: vector<int> simulate(int w, int h, int x, int y) fa7992ffc5 2012-08-06 kinaba: { fa7992ffc5 2012-08-06 kinaba: vector<int> moves; fa7992ffc5 2012-08-06 kinaba: vector< vector<bool> > vis(h, vector<bool>(w)); fa7992ffc5 2012-08-06 kinaba: int dx[]={+1,0,-1,0}; fa7992ffc5 2012-08-06 kinaba: int dy[]={0,+1,0,-1}; fa7992ffc5 2012-08-06 kinaba: int d = 0; fa7992ffc5 2012-08-06 kinaba: vis[y][x] = true; fa7992ffc5 2012-08-06 kinaba: for(;;) { fa7992ffc5 2012-08-06 kinaba: int cnt = 0; fa7992ffc5 2012-08-06 kinaba: for(;;) { fa7992ffc5 2012-08-06 kinaba: int xx=x+dx[d]; fa7992ffc5 2012-08-06 kinaba: int yy=y+dy[d]; fa7992ffc5 2012-08-06 kinaba: if( yy<0||h<=yy||xx<0||w<=xx||vis[yy][xx] ) fa7992ffc5 2012-08-06 kinaba: break; fa7992ffc5 2012-08-06 kinaba: y=yy, x=xx; fa7992ffc5 2012-08-06 kinaba: vis[y][x] = true; fa7992ffc5 2012-08-06 kinaba: ++cnt; fa7992ffc5 2012-08-06 kinaba: } fa7992ffc5 2012-08-06 kinaba: d = (d+1)%4; fa7992ffc5 2012-08-06 kinaba: if( cnt == 0 ) fa7992ffc5 2012-08-06 kinaba: break; fa7992ffc5 2012-08-06 kinaba: moves.push_back(cnt); fa7992ffc5 2012-08-06 kinaba: } fa7992ffc5 2012-08-06 kinaba: return moves; fa7992ffc5 2012-08-06 kinaba: } fa7992ffc5 2012-08-06 kinaba: fa7992ffc5 2012-08-06 kinaba: bool match(const vector<int>& rm, const vector<int>& m) fa7992ffc5 2012-08-06 kinaba: { fa7992ffc5 2012-08-06 kinaba: if(rm.size() < m.size()) fa7992ffc5 2012-08-06 kinaba: return false; fa7992ffc5 2012-08-06 kinaba: for(int i=0; i+1<m.size(); ++i) fa7992ffc5 2012-08-06 kinaba: if(rm[i] != m[i]) fa7992ffc5 2012-08-06 kinaba: return false; fa7992ffc5 2012-08-06 kinaba: return rm[m.size()-1] >= m[m.size()-1]; fa7992ffc5 2012-08-06 kinaba: } fa7992ffc5 2012-08-06 kinaba: }; fa7992ffc5 2012-08-06 kinaba: fa7992ffc5 2012-08-06 kinaba: // BEGIN CUT HERE fa7992ffc5 2012-08-06 kinaba: #include <ctime> fa7992ffc5 2012-08-06 kinaba: double start_time; string timer() fa7992ffc5 2012-08-06 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } fa7992ffc5 2012-08-06 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) fa7992ffc5 2012-08-06 kinaba: { os << "{ "; fa7992ffc5 2012-08-06 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) fa7992ffc5 2012-08-06 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } fa7992ffc5 2012-08-06 kinaba: void verify_case(const int& Expected, const int& Received) { fa7992ffc5 2012-08-06 kinaba: bool ok = (Expected == Received); fa7992ffc5 2012-08-06 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; fa7992ffc5 2012-08-06 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } fa7992ffc5 2012-08-06 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); fa7992ffc5 2012-08-06 kinaba: #define END verify_case(_, RotatingBot().minArea(moves));} fa7992ffc5 2012-08-06 kinaba: int main(){ fa7992ffc5 2012-08-06 kinaba: fa7992ffc5 2012-08-06 kinaba: CASE(0) fa7992ffc5 2012-08-06 kinaba: int moves_[] = {15}; fa7992ffc5 2012-08-06 kinaba: vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); fa7992ffc5 2012-08-06 kinaba: int _ = 16; fa7992ffc5 2012-08-06 kinaba: END fa7992ffc5 2012-08-06 kinaba: CASE(1) fa7992ffc5 2012-08-06 kinaba: int moves_[] = {3,10}; fa7992ffc5 2012-08-06 kinaba: vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); fa7992ffc5 2012-08-06 kinaba: int _ = 44; fa7992ffc5 2012-08-06 kinaba: END fa7992ffc5 2012-08-06 kinaba: CASE(2) fa7992ffc5 2012-08-06 kinaba: int moves_[] = {1,1,1,1}; fa7992ffc5 2012-08-06 kinaba: vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); fa7992ffc5 2012-08-06 kinaba: int _ = -1; fa7992ffc5 2012-08-06 kinaba: END fa7992ffc5 2012-08-06 kinaba: CASE(3) fa7992ffc5 2012-08-06 kinaba: int moves_[] = {9,5,11,10,11,4,10}; fa7992ffc5 2012-08-06 kinaba: vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); fa7992ffc5 2012-08-06 kinaba: int _ = 132; fa7992ffc5 2012-08-06 kinaba: END fa7992ffc5 2012-08-06 kinaba: CASE(4) fa7992ffc5 2012-08-06 kinaba: int moves_[] = {12,1,27,14,27,12,26,11,25,10,24,9,23,8,22,7,21,6,20,5,19,4,18,3,17,2,16,1,15}; fa7992ffc5 2012-08-06 kinaba: vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); fa7992ffc5 2012-08-06 kinaba: int _ = 420; fa7992ffc5 2012-08-06 kinaba: END fa7992ffc5 2012-08-06 kinaba: CASE(5) fa7992ffc5 2012-08-06 kinaba: int moves_[] = {8,6,6,1}; fa7992ffc5 2012-08-06 kinaba: vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); fa7992ffc5 2012-08-06 kinaba: int _ = -1; fa7992ffc5 2012-08-06 kinaba: END fa7992ffc5 2012-08-06 kinaba: CASE(6) fa7992ffc5 2012-08-06 kinaba: int moves_[] = {8,6,6}; fa7992ffc5 2012-08-06 kinaba: vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); fa7992ffc5 2012-08-06 kinaba: int _ = 63; fa7992ffc5 2012-08-06 kinaba: END fa7992ffc5 2012-08-06 kinaba: CASE(7) fa7992ffc5 2012-08-06 kinaba: int moves_[] = {5,4,5,3,3}; fa7992ffc5 2012-08-06 kinaba: vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); fa7992ffc5 2012-08-06 kinaba: int _ = 30; fa7992ffc5 2012-08-06 kinaba: END fa7992ffc5 2012-08-06 kinaba: CASE(8) fa7992ffc5 2012-08-06 kinaba: int moves_[] = {2,2,2,1}; fa7992ffc5 2012-08-06 kinaba: vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); fa7992ffc5 2012-08-06 kinaba: int _ = 9; fa7992ffc5 2012-08-06 kinaba: END fa7992ffc5 2012-08-06 kinaba: /* fa7992ffc5 2012-08-06 kinaba: CASE(9) fa7992ffc5 2012-08-06 kinaba: int moves_[] = ; fa7992ffc5 2012-08-06 kinaba: vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); fa7992ffc5 2012-08-06 kinaba: int _ = ; fa7992ffc5 2012-08-06 kinaba: END fa7992ffc5 2012-08-06 kinaba: */ fa7992ffc5 2012-08-06 kinaba: } fa7992ffc5 2012-08-06 kinaba: // END CUT HERE