Overview
| SHA1 Hash: | 9298d17feb290f25c6c332e70ea703d7a689c734 |
|---|---|
| Date: | 2020-08-18 09:44:50 |
| User: | kinaba |
| Comment: | TCO3A |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
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 + > 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, > 56 // ==> (0,0) -> (0, y1-1) -> (x1-1, y1-1) -> (x2+1, y) -> (x, > 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) > 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 > 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() > 106 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 107 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 108 #define END verify_case(_, RectangularObstacle().countReachable(x1, x2, y1, > 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