• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Added SRM/TCO20-3A-U/1A-U.cpp version [52ba9270e5567c22]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <tuple>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class RectangularObstacle { public:
           23  + long long countReachable(int x1_, int x2_, int y1_, int y2_, int s_)
           24  + {
           25  +  LL x1 = x1_, x2 = x2_, y1 = y1_, y2 = y2_, s=s_;
           26  +  LL answer = 0;
           27  +
           28  +  answer += pyramid(s, s);
           29  +  answer += 2 * s + 1;
           30  +  answer += pyramid(s, min(s, y2));
           31  +
           32  +  for (LL y=y1; y<=y2 && y<=s; ++y) {
           33  +  }
           34  +  // [-s, -1]
           35  +  //    ==> 1 + 3 + 5 + .. + (2*s-1)
           36  +  answer += (1LL + 2*s - 1) * s / 2;
           37  +
           38  +  // [0, y1-1]
           39  +  //    ==> (2*s+1) + (2*s-1) + (2*s-3) + ...
           40  +  LL ymax_case2 = min(y1 - 1, s);
           41  +  answer += (2 * s + 1 + 2 * (s - ymax_case2) + 1) * (ymax_case2 + 1) / 2;
           42  +  cerr << answer << endl;
           43  +  if (s < y1)
           44  +   return answer;
           45  +
           46  +  // [y1, y2]
           47  +  //    ==> normal, but [x1,x2] subtracted
           48  +  answer += case3(s - y1, x2, y2 - y1 + 1);
           49  +  answer += case3(s - y1, -x1, y2 - y1 + 1);
           50  +  cerr << answer << endl;
           51  +  if (s <= y2)
           52  +   return answer;
           53  +
           54  +  // [y2+1, +s] : min
           55  +  //    ==> (0,0) -> (0, y1-1) -> (x2+1, y1-1) -> (x2+1, y) -> (x,y)
           56  +  //    ==> (0,0) -> (0, y1-1) -> (x1-1, y1-1) -> (x2+1, y) -> (x,y)
           57  +  LL ls = -x1 + 1 + y2 + 1;  // (x1-1, y2+1)
           58  +  LL rs = x2 + 1 + y2 + 1;   // (x2+1, y2+1)
           59  +  answer += case4(x1 - 1, s - ls, x2 + 1, s - rs);
           60  +  return answer;
           61  + }
           62  +
           63  + static LL pyramid(LL s, LL h) {
           64  +  return (2 * s - 1 + 2 * s - 1 - 2 * h) * h / 2;
           65  + }
           66  +
           67  + static LL case3(LL len, LL obs, LL cnt) {
           68  +  cerr << len << " " << obs << " " << cnt << endl;
           69  +  cnt = max(0LL, min(cnt, len - obs));
           70  +  cerr << (len-obs + len-obs - (cnt - 1)) * cnt / 2 << endl;
           71  +  return (len + len - (cnt - 1)) * cnt / 2;
           72  + }
           73  +
           74  + static LL case4(LL x1, LL s1, LL x2, LL s2) {
           75  +  cerr << x1 << " " << s1 << " " << x2 << " " << s2 << endl;
           76  +  LL answer = 0;
           77  +  if (s1 >= 0) answer += simp(s1);
           78  +  if (s2 >= 0) answer += simp(s2);
           79  +  if (s1 >= 0 && s2 >= 0) {
           80  +   LL xl = x2 - s2;
           81  +   LL xr = x1 + s1;
           82  +   if (xl <= xr) {
           83  +    LL w = xr - xl + 1;
           84  +    answer -= (w + w%2) * (w/2+1) / 2;
           85  +   }
           86  +  }
           87  +  return answer;
           88  + }
           89  +
           90  + static LL simp(LL s) {
           91  +  return (1 + 2 * s + 1) * (s + 1) / 2;
           92  + }
           93  +};
           94  +
           95  +// BEGIN CUT HERE
           96  +#include <ctime>
           97  +double start_time; string timer()
           98  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           99  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          100  + { os << "{ ";
          101  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          102  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          103  +void verify_case(const long long& Expected, const long long& Received) {
          104  + bool ok = (Expected == Received);
          105  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          106  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          107  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          108  +#define END  verify_case(_, RectangularObstacle().countReachable(x1, x2, y1, y2, s));}
          109  +int main(){
          110  +
          111  +CASE(0)
          112  + int x1 = -5;
          113  + int x2 = 5;
          114  + int y1 = 3;
          115  + int y2 = 3;
          116  + int s = 2;
          117  + long long _ = 13LL;
          118  +END
          119  +CASE(1)
          120  + int x1 = -5;
          121  + int x2 = 5;
          122  + int y1 = 3;
          123  + int y2 = 3;
          124  + int s = 3;
          125  + long long _ = 24LL;
          126  +END
          127  +CASE(2)
          128  + int x1 = -4;
          129  + int x2 = 1;
          130  + int y1 = 1;
          131  + int y2 = 2;
          132  + int s = 6;
          133  + long long _ = 61LL;
          134  +END
          135  +CASE(3)
          136  + int x1 = 0;
          137  + int x2 = 0;
          138  + int y1 = 1;
          139  + int y2 = 1;
          140  + int s = 4;
          141  + long long _ = 38LL;
          142  +END
          143  +CASE(4)
          144  + int x1 = -100;
          145  + int x2 = 100;
          146  + int y1 = 42;
          147  + int y2 = 47;
          148  + int s = 0;
          149  + long long _ = 1LL;
          150  +END
          151  +CASE(5)
          152  + int x1 = -1000000;
          153  + int x2 = +1000000;
          154  + int y1 = +500000;
          155  + int y2 = +1000000;
          156  + int s = +1000000000;
          157  + long long _ = -1LL;
          158  +END
          159  +CASE(6)
          160  + int x1 = -0;
          161  + int x2 = +0;
          162  + int y1 = 1;
          163  + int y2 = 1;
          164  + int s = 2;
          165  + long long _ = -1LL;
          166  +END
          167  +}
          168  +// END CUT HERE