2b07d53d04 2012-07-07 kinaba: #include <iostream> 2b07d53d04 2012-07-07 kinaba: #include <sstream> 2b07d53d04 2012-07-07 kinaba: #include <iomanip> 2b07d53d04 2012-07-07 kinaba: #include <vector> 2b07d53d04 2012-07-07 kinaba: #include <string> 2b07d53d04 2012-07-07 kinaba: #include <map> 2b07d53d04 2012-07-07 kinaba: #include <set> 2b07d53d04 2012-07-07 kinaba: #include <algorithm> 2b07d53d04 2012-07-07 kinaba: #include <numeric> 2b07d53d04 2012-07-07 kinaba: #include <iterator> 2b07d53d04 2012-07-07 kinaba: #include <functional> 2b07d53d04 2012-07-07 kinaba: #include <complex> 2b07d53d04 2012-07-07 kinaba: #include <queue> 2b07d53d04 2012-07-07 kinaba: #include <stack> 2b07d53d04 2012-07-07 kinaba: #include <cmath> 2b07d53d04 2012-07-07 kinaba: #include <cassert> 2b07d53d04 2012-07-07 kinaba: using namespace std; 2b07d53d04 2012-07-07 kinaba: typedef long long LL; 2b07d53d04 2012-07-07 kinaba: typedef long double LD; 2b07d53d04 2012-07-07 kinaba: typedef complex<LD> CMP; 2b07d53d04 2012-07-07 kinaba: 2b07d53d04 2012-07-07 kinaba: class KingdomAndTrees { public: 2b07d53d04 2012-07-07 kinaba: int minLevel(vector <int> heights) 2b07d53d04 2012-07-07 kinaba: { 2b07d53d04 2012-07-07 kinaba: // (L,R] 2b07d53d04 2012-07-07 kinaba: int L = -1; 2b07d53d04 2012-07-07 kinaba: int R = 1000000000; 2b07d53d04 2012-07-07 kinaba: while(R-L>1) 2b07d53d04 2012-07-07 kinaba: { 2b07d53d04 2012-07-07 kinaba: int C = (L+R)/2; 2b07d53d04 2012-07-07 kinaba: (possible(C,heights) ? R : L) = C; 2b07d53d04 2012-07-07 kinaba: } 2b07d53d04 2012-07-07 kinaba: return R; 2b07d53d04 2012-07-07 kinaba: } 2b07d53d04 2012-07-07 kinaba: 2b07d53d04 2012-07-07 kinaba: bool possible(int C, const vector<int>& h) 2b07d53d04 2012-07-07 kinaba: { 2b07d53d04 2012-07-07 kinaba: int last = max(1, h[0]-C); 2b07d53d04 2012-07-07 kinaba: for(int i=1; i<h.size(); ++i) 2b07d53d04 2012-07-07 kinaba: { 2b07d53d04 2012-07-07 kinaba: if( !(last < h[i]+C) ) 2b07d53d04 2012-07-07 kinaba: return false; 2b07d53d04 2012-07-07 kinaba: last = max(last+1, h[i]-C); 2b07d53d04 2012-07-07 kinaba: } 2b07d53d04 2012-07-07 kinaba: return true; 2b07d53d04 2012-07-07 kinaba: } 2b07d53d04 2012-07-07 kinaba: }; 2b07d53d04 2012-07-07 kinaba: 2b07d53d04 2012-07-07 kinaba: // BEGIN CUT HERE 2b07d53d04 2012-07-07 kinaba: #include <ctime> 2b07d53d04 2012-07-07 kinaba: double start_time; string timer() 2b07d53d04 2012-07-07 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 2b07d53d04 2012-07-07 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 2b07d53d04 2012-07-07 kinaba: { os << "{ "; 2b07d53d04 2012-07-07 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 2b07d53d04 2012-07-07 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 2b07d53d04 2012-07-07 kinaba: void verify_case(const int& Expected, const int& Received) { 2b07d53d04 2012-07-07 kinaba: bool ok = (Expected == Received); 2b07d53d04 2012-07-07 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 2b07d53d04 2012-07-07 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 2b07d53d04 2012-07-07 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 2b07d53d04 2012-07-07 kinaba: #define END verify_case(_, KingdomAndTrees().minLevel(heights));} 2b07d53d04 2012-07-07 kinaba: int main(){ 2b07d53d04 2012-07-07 kinaba: 2b07d53d04 2012-07-07 kinaba: CASE(0) 2b07d53d04 2012-07-07 kinaba: int heights_[] = {9, 5, 11}; 2b07d53d04 2012-07-07 kinaba: vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_)); 2b07d53d04 2012-07-07 kinaba: int _ = 3; 2b07d53d04 2012-07-07 kinaba: END 2b07d53d04 2012-07-07 kinaba: CASE(1) 2b07d53d04 2012-07-07 kinaba: int heights_[] = {5, 8}; 2b07d53d04 2012-07-07 kinaba: vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_)); 2b07d53d04 2012-07-07 kinaba: int _ = 0; 2b07d53d04 2012-07-07 kinaba: END 2b07d53d04 2012-07-07 kinaba: CASE(2) 2b07d53d04 2012-07-07 kinaba: int heights_[] = {1, 1, 1, 1, 1}; 2b07d53d04 2012-07-07 kinaba: vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_)); 2b07d53d04 2012-07-07 kinaba: int _ = 4; 2b07d53d04 2012-07-07 kinaba: END 2b07d53d04 2012-07-07 kinaba: CASE(3) 2b07d53d04 2012-07-07 kinaba: int heights_[] = {548, 47, 58, 250, 2012}; 2b07d53d04 2012-07-07 kinaba: vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_)); 2b07d53d04 2012-07-07 kinaba: int _ = 251; 2b07d53d04 2012-07-07 kinaba: END 2b07d53d04 2012-07-07 kinaba: CASE(4) 2b07d53d04 2012-07-07 kinaba: int heights_[] = {337994619,837714986,7014426,516695490,268514071,590654553,940024470,79308071,891444369,231310251,172567010,283491054,951215936,92716118,911004789,896372476,617116292,874491895,120052194,635772188,938392572,466867891,418351197,278475278,635224368,38779964,762367612,370214557,20108108,314281202,644947239,868648377,617056931,542328796,280916141,281585869,895175595,529854516,862330692,733665485,173060292,579136324,401396401,303236137,161627936,410922706,172892990,840336279,848958999,849348801}; 2b07d53d04 2012-07-07 kinaba: vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_)); 2b07d53d04 2012-07-07 kinaba: int _ = -1; 2b07d53d04 2012-07-07 kinaba: END 2b07d53d04 2012-07-07 kinaba: CASE(5) 2b07d53d04 2012-07-07 kinaba: int heights_[] = {1000000000,1}; 2b07d53d04 2012-07-07 kinaba: vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_)); 2b07d53d04 2012-07-07 kinaba: int _ = 500000000; 2b07d53d04 2012-07-07 kinaba: END 2b07d53d04 2012-07-07 kinaba: 2b07d53d04 2012-07-07 kinaba: } 2b07d53d04 2012-07-07 kinaba: // END CUT HERE