ddf2358d33 2012-08-08 kinaba: #include <iostream> ddf2358d33 2012-08-08 kinaba: #include <sstream> ddf2358d33 2012-08-08 kinaba: #include <iomanip> ddf2358d33 2012-08-08 kinaba: #include <vector> ddf2358d33 2012-08-08 kinaba: #include <string> ddf2358d33 2012-08-08 kinaba: #include <map> ddf2358d33 2012-08-08 kinaba: #include <set> ddf2358d33 2012-08-08 kinaba: #include <algorithm> ddf2358d33 2012-08-08 kinaba: #include <numeric> ddf2358d33 2012-08-08 kinaba: #include <iterator> ddf2358d33 2012-08-08 kinaba: #include <functional> ddf2358d33 2012-08-08 kinaba: #include <complex> ddf2358d33 2012-08-08 kinaba: #include <queue> ddf2358d33 2012-08-08 kinaba: #include <stack> ddf2358d33 2012-08-08 kinaba: #include <cmath> ddf2358d33 2012-08-08 kinaba: #include <cassert> ddf2358d33 2012-08-08 kinaba: using namespace std; ddf2358d33 2012-08-08 kinaba: typedef long long LL; ddf2358d33 2012-08-08 kinaba: typedef long double LD; ddf2358d33 2012-08-08 kinaba: typedef complex<LD> CMP; ddf2358d33 2012-08-08 kinaba: ddf2358d33 2012-08-08 kinaba: class KingdomAndTrees { public: ddf2358d33 2012-08-08 kinaba: int minLevel(vector <int> heights) ddf2358d33 2012-08-08 kinaba: { ddf2358d33 2012-08-08 kinaba: // (L,R] ddf2358d33 2012-08-08 kinaba: int L = -1; ddf2358d33 2012-08-08 kinaba: int R = 1000000000; ddf2358d33 2012-08-08 kinaba: while(R-L>1) ddf2358d33 2012-08-08 kinaba: { ddf2358d33 2012-08-08 kinaba: int C = (L+R)/2; ddf2358d33 2012-08-08 kinaba: (possible(C,heights) ? R : L) = C; ddf2358d33 2012-08-08 kinaba: } ddf2358d33 2012-08-08 kinaba: return R; ddf2358d33 2012-08-08 kinaba: } ddf2358d33 2012-08-08 kinaba: ddf2358d33 2012-08-08 kinaba: bool possible(int C, const vector<int>& h) ddf2358d33 2012-08-08 kinaba: { ddf2358d33 2012-08-08 kinaba: int last = max(1, h[0]-C); ddf2358d33 2012-08-08 kinaba: for(int i=1; i<h.size(); ++i) ddf2358d33 2012-08-08 kinaba: { ddf2358d33 2012-08-08 kinaba: if( !(last < h[i]+C) ) ddf2358d33 2012-08-08 kinaba: return false; ddf2358d33 2012-08-08 kinaba: last = max(last+1, h[i]-C); ddf2358d33 2012-08-08 kinaba: } ddf2358d33 2012-08-08 kinaba: return true; ddf2358d33 2012-08-08 kinaba: } ddf2358d33 2012-08-08 kinaba: }; ddf2358d33 2012-08-08 kinaba: ddf2358d33 2012-08-08 kinaba: // BEGIN CUT HERE ddf2358d33 2012-08-08 kinaba: #include <ctime> ddf2358d33 2012-08-08 kinaba: double start_time; string timer() ddf2358d33 2012-08-08 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } ddf2358d33 2012-08-08 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) ddf2358d33 2012-08-08 kinaba: { os << "{ "; ddf2358d33 2012-08-08 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) ddf2358d33 2012-08-08 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } ddf2358d33 2012-08-08 kinaba: void verify_case(const int& Expected, const int& Received) { ddf2358d33 2012-08-08 kinaba: bool ok = (Expected == Received); ddf2358d33 2012-08-08 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; ddf2358d33 2012-08-08 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } ddf2358d33 2012-08-08 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); ddf2358d33 2012-08-08 kinaba: #define END verify_case(_, KingdomAndTrees().minLevel(heights));} ddf2358d33 2012-08-08 kinaba: int main(){ ddf2358d33 2012-08-08 kinaba: ddf2358d33 2012-08-08 kinaba: CASE(0) ddf2358d33 2012-08-08 kinaba: int heights_[] = {9, 5, 11}; ddf2358d33 2012-08-08 kinaba: vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_)); ddf2358d33 2012-08-08 kinaba: int _ = 3; ddf2358d33 2012-08-08 kinaba: END ddf2358d33 2012-08-08 kinaba: CASE(1) ddf2358d33 2012-08-08 kinaba: int heights_[] = {5, 8}; ddf2358d33 2012-08-08 kinaba: vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_)); ddf2358d33 2012-08-08 kinaba: int _ = 0; ddf2358d33 2012-08-08 kinaba: END ddf2358d33 2012-08-08 kinaba: CASE(2) ddf2358d33 2012-08-08 kinaba: int heights_[] = {1, 1, 1, 1, 1}; ddf2358d33 2012-08-08 kinaba: vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_)); ddf2358d33 2012-08-08 kinaba: int _ = 4; ddf2358d33 2012-08-08 kinaba: END ddf2358d33 2012-08-08 kinaba: CASE(3) ddf2358d33 2012-08-08 kinaba: int heights_[] = {548, 47, 58, 250, 2012}; ddf2358d33 2012-08-08 kinaba: vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_)); ddf2358d33 2012-08-08 kinaba: int _ = 251; ddf2358d33 2012-08-08 kinaba: END ddf2358d33 2012-08-08 kinaba: CASE(4) ddf2358d33 2012-08-08 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}; ddf2358d33 2012-08-08 kinaba: vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_)); ddf2358d33 2012-08-08 kinaba: int _ = -1; ddf2358d33 2012-08-08 kinaba: END ddf2358d33 2012-08-08 kinaba: CASE(5) ddf2358d33 2012-08-08 kinaba: int heights_[] = {1000000000,1}; ddf2358d33 2012-08-08 kinaba: vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_)); ddf2358d33 2012-08-08 kinaba: int _ = 500000000; ddf2358d33 2012-08-08 kinaba: END ddf2358d33 2012-08-08 kinaba: ddf2358d33 2012-08-08 kinaba: } ddf2358d33 2012-08-08 kinaba: // END CUT HERE