bool_bool

UVa - 11906

Nov 24th, 2019
183
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.73 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <sstream>
  6. #include <cstring>
  7. #include <string>
  8. #include <set>
  9. #include <complex>
  10. #include <map>
  11. #include <unordered_map>
  12. #include <climits>
  13. #include <bitset>
  14. #include <queue>
  15. #include <chrono>
  16. #include <random>
  17. #include <typeinfo>
  18. #include <stack>
  19. #include <list>
  20. using namespace std;
  21.  
  22. #define all(v) v.begin(), v.end()
  23. #define Chrono chrono::steady_clock::now().time_since_epoch().count()
  24. #define dist2D(x1, y1, x2, y2) ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))
  25. #define dist3D(x1, y1, z1, x2, y2, z2) ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) + (z1 - z2) * (z1 - z2))
  26. #define EPS 1e-15
  27. #define endl "\n"
  28. #define FastIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
  29. #define FI freopen("in.txt", "r", stdin)
  30. #define FO freopen("out.txt", "w", stdout)
  31. #define ff first
  32. #define INF 1000000000000000000
  33. #define ld long double
  34. #define ll long long
  35. #define mem(x,y) memset(x, y, sizeof x)
  36. #define mp make_pair
  37. #define msi map<string, int>
  38. #define mii map<int, int>
  39. #define mis map<int, string>
  40. #define MOD 1000000007
  41. #define PI acos(-1.0)
  42. #define PQ priority_queue
  43. #define pb push_back
  44. #define pib pair<int, bool>
  45. #define pii pair<int, int>
  46. #define pll pair<ll, ll>
  47. #define present(c, x) ((c).find(x) != (c).end())
  48. #define sfi(x) scanf("%d", &x)
  49. #define sfii(x,y) scanf("%d %d", &x, &y)
  50. #define sfiii(x,y,z) scanf("%d %d %d", &x, &y, &z)
  51. #define siz(x) (int)x.size()
  52. #define ss second
  53. #define timeTaken endd = clock(); cout << (double) (endd - beginn) / CLOCKS_PER_SEC * 1000 << endl
  54. #define timeInit clock_t beginn = clock(), endd
  55. #define ull unsigned long long
  56. #define umsi unordered_map<string, int>
  57. #define umii unordered_map<int, int>
  58. #define umis unordered_map<int, string>
  59. #define vb vector<bool>
  60. #define vi vector<int>
  61. #define vvi vector<vi>
  62. #define vii vector<pii>
  63. #define vvii vector<vii>
  64. #define vll vector<ll>
  65. #define vvll vector<vll>
  66. #define vpll vector<pll>
  67. #define bug(...) cerr << __PRETTY_FUNCTION__ << " - " << __LINE__ << " : (" << #__VA_ARGS__ << ") = ("; _Print(__VA_ARGS__);
  68. template<class T> void _Print(T &&x) { cerr << x << ")" << endl; }
  69. template<class T, class ...S> void _Print(T &&x, S &&...y) { cerr << x << ", "; _Print(y...); }
  70.  
  71. /*
  72. #include <ext/pb_ds/assoc_container.hpp>
  73. #include <ext/pb_ds/tree_policy.hpp>
  74. #include <functional>
  75. using namespace __gnu_pbds;
  76. typedef tree<int,null_type, less<int>, rb_tree_tag,
  77. tree_order_statistics_node_update> ordered_set;
  78.  
  79. //os.order_of_key(v): returns how many elements strictly less than v
  80. //os.find_by_order(k - 1): returns kth smallest element's iterator
  81. */
  82.  
  83. template<class T> class compare {
  84. public:
  85. bool operator() (pair<T, T> &x, pair<T, T> &y) {
  86. if (x.first == y.first) {
  87. return x.ss > y.ss;
  88. }
  89. return x.ff > y.ff;
  90. }
  91. };
  92.  
  93. template<class T> ostream &operator<<(ostream &os, const pair<T, T> &a) { return os << a.ff << " " << a.ss; }
  94. ll power(ll a, int b) {
  95. ll po = 1;
  96. while (b) {
  97. if (b & 1)
  98. po *= a;
  99. a *= a;
  100. b >>= 1;
  101. }
  102. return po;
  103. }
  104.  
  105. template<class T> pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return {a.ff + b.ff, a.ss + b.ss}; }
  106. template<class T> pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return {a.ff - b.ff, a.ss - b.ss}; }
  107. template<class T> pair<T, T> operator*(const pair<T, T> &a, const pair<T, T> &b) { return {a.ff * b.ff, a.ss * b.ss}; }
  108. template<class T> pair<T, T> operator%(const pair<T, T> &a, const pair<T, T> &b) { return {a.ff % b.ff, a.ss % b.ss}; }
  109. template<class T, class U> pair<T, T> operator+(const pair<T, T> &a, const U &b) { return {a.ff + b, a.ss + b}; }
  110. template<class T, class U> pair<T, T> operator*(const pair<T, T> &a, const U &b) { return {a.ff * b, a.ss * b}; }
  111.  
  112. int Set(int N, int pos) { return N = N | (1 << pos); }
  113. int reset(int N, int pos){ return N = N & ~ (1 << pos); }
  114. bool check(int N, int pos){ return (bool) (N & (1 << pos)); }
  115.  
  116. ///=======================================template=======================================///
  117.  
  118. int main() {
  119.  
  120. int t;
  121. cin >> t;
  122. for (int tc = 1; tc <= t; tc++) {
  123. int r, c, m, n, even = 0, odd = 0;
  124. cin >> r >> c >> m >> n;
  125. vvi vis(r, vi(c, 0));
  126.  
  127. int w;
  128. cin >> w;
  129. while (w--) {
  130. int x, y;
  131. cin >> x >> y;
  132. vis[x][y] = 2;
  133. }
  134.  
  135. if (m < n)
  136. swap(m, n);
  137. pii dir[8];
  138. int sign = 1;
  139. for (int i = 0; i < 4;) {
  140. dir[i] = {sign * m, n};
  141. dir[i + 1] = {sign * m, -n};
  142. i += 2;
  143. sign *= -1;
  144. }
  145. for (int i = 4; i < 8;) {
  146. dir[i] = {n, sign * m};
  147. dir[i + 1] = {-n, sign * m};
  148. i += 2;
  149. sign *= -1;
  150. }
  151.  
  152. vii points;
  153. points.pb({0, 0});
  154. int to = (m == n ? 4 : 8);
  155. while (!points.empty()) {
  156. pii p = points.back();
  157. //bug(p.ff, p.ss);
  158. points.pop_back();
  159. vis[p.ff][p.ss] = 1;
  160. int cnt = 0;
  161. for (int i = 0; i < to; i++) {
  162. int tox = p.ff + dir[i].ff, toy = p.ss + dir[i].ss;
  163. if (tox >= 0 and tox < r and toy >= 0 and toy < c and vis[tox][toy] != 2) {
  164. cnt++;
  165. if (vis[tox][toy] == 0) {
  166. points.pb({tox, toy});
  167. vis[tox][toy] = 1;
  168. }
  169. }
  170. }
  171.  
  172. if (cnt & 1)
  173. odd++;
  174. else even++;
  175.  
  176. }
  177.  
  178. cout << "Case " << tc << ": " << even << " " << odd << endl;
  179. }
  180.  
  181. return 0;
  182. }
Advertisement
Add Comment
Please, Sign In to add comment