Advertisement
Galebickosikasa

Untitled

Jan 13th, 2021
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.19 KB | None | 0 0
  1. #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
  2. // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx")
  3. // #pragma comment(linker, "/stack:200000000"]
  4.  
  5. #include <iostream>
  6. #include <vector>
  7. #include <cmath>
  8. #include <algorithm>
  9. #include <unordered_set>
  10. #include <unordered_map>
  11. #include <set>
  12. #include <map>
  13. #include <queue>
  14. #include <deque>
  15. #include <bitset>
  16. #include <stack>
  17. #include <random>
  18. #include <fstream>
  19. #include <sstream>
  20. #include <chrono>
  21.  
  22. #define fi first
  23. #define se second
  24. #define pb push_back
  25. #define ll long long
  26. #define ld long double
  27. #define hm unordered_map
  28. #define pii pair<int, int>
  29. #define sz(a) (int)a.size()
  30. #define all(a) a.begin(), a.end()
  31. #define cinv(v) for (auto& x: v) cin >> x
  32. #define fr(i, n) for (int i = 0; i < n; ++i)
  33. #define fl(i, l, n) for (int i = l; i < n; ++i)
  34.  
  35. // #define int ll
  36.  
  37. template <typename T1, typename T2> inline bool chkmin(T1 &x, const T2 &y) {if (x > y) {x = y; return 1;} return 0;}
  38. template <typename T1, typename T2> inline bool chkmax(T1 &x, const T2 &y) {if (x < y) {x = y; return 1;} return 0;}
  39.  
  40. using namespace std;
  41.  
  42. #ifdef LOCAL
  43. #define dbg(x) cerr << #x << " : " << x << '\n'
  44. const int maxn = 1000 + 20;
  45. #else
  46. #define dbg(x)
  47. const int maxn = 1000 + 20;
  48. #endif
  49.  
  50. //tg: @runningcherry
  51.  
  52. ostream& operator << (ostream& out, const pii& v) {
  53. out << v.fi << ", " << v.se;
  54. return out;
  55. }
  56.  
  57. template<typename T> ostream& operator << (ostream& out, const vector<T>& v) {
  58. for (auto& x: v) out << x << " ";
  59. return out;
  60. }
  61.  
  62. istream& operator >> (istream& in, pii& a) {
  63. in >> a.fi >> a.se;
  64. return in;
  65. }
  66.  
  67. const ll inf = (ll) 2e9;
  68. const ld pi = asin (1) * 2;
  69. const ld eps = 1e-8;
  70. const ll mod = (ll)1e9 + 7;
  71. const ll ns = 97;
  72.  
  73. mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  74.  
  75. int t[maxn * maxn], sz[maxn * maxn];
  76.  
  77. struct DSU {
  78. vector<vector<int>> order;
  79.  
  80. DSU (int n) {
  81. for (int i = 0; i < n; ++i) {
  82. t[i] = i;
  83. sz[i] = 1;
  84. }
  85. }
  86.  
  87. inline void rollback () {
  88. auto ta = order.back ()[0], a = order.back ()[1], b = order.back ()[2], szb = order.back ()[3];
  89. order.pop_back ();
  90. t[a] = ta;
  91. sz[b] = szb;
  92. }
  93.  
  94. inline int get (int x) {
  95. while (t[x] != x) x = t[x];
  96. return x;
  97. }
  98.  
  99. inline void join1 (int a, int b) {
  100. a = get (a), b = get (b);
  101. if (a != b) {
  102. if (sz[a] > sz[b]) swap (a, b);
  103. t[a] = b;
  104. sz[b] += sz[a];
  105. }
  106. }
  107.  
  108. inline int join (int a, int b) {
  109. a = get (a), b = get (b);
  110. if (a != b) {
  111. if (sz[a] > sz[b]) swap (a, b);
  112. order.pb ({t[a], a, b, sz[b]});
  113. t[a] = b;
  114. sz[b] += sz[a];
  115. return 1;
  116. }
  117. return 0;
  118. }
  119. };
  120.  
  121. int goo[maxn][maxn], n, m, ans = 0;
  122. vector<pii> d = {{0, 1}, {1, 0}};
  123. vector<pii> kek[maxn * maxn * 2];
  124. pii res = {-1, -1};
  125.  
  126. inline int corr (int i, int j) {
  127. return i >= 0 && j >= 0 && i < n && j < m;
  128. }
  129.  
  130. signed main () {
  131. ios_base::sync_with_stdio(false);
  132. cin.tie(nullptr);
  133. cout.tie(nullptr);
  134. cin >> n >> m;
  135. DSU dsu (n * m);
  136. for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) cin >> goo[i][j];
  137. for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) for (auto& x: d) {
  138. int ii = i + x.fi, jj = j + x.se;
  139. if (corr (ii, jj) && goo[i][j] == goo[ii][jj]) dsu.join1 (i * m + j, ii * m + jj);
  140. }
  141. map <pii, int> num;
  142. int last = 0;
  143. for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) for (auto& x: d) {
  144. int ii = i + x.fi, jj = j + x.se;
  145. if (corr (ii, jj) && goo[i][j] != goo[ii][jj]) {
  146. pii ptt = {goo[i][j], goo[ii][jj]};
  147. if (ptt.fi > ptt.se) swap (ptt.fi, ptt.se);
  148. int x;
  149. auto it = num.find (ptt);
  150. if (it == num.end ()) {
  151. x = last;
  152. num[ptt] = last++;
  153. } else {
  154. x = it->se;
  155. }
  156. kek[x].pb ({i * m + j, ii * m + jj});
  157. }
  158. }
  159. for (auto& r: num) {
  160. int i = r.se;
  161. int counter = 0;
  162. for (auto& x: kek[i]) counter += dsu.join (x.fi, x.se);
  163. for (auto& x: kek[i]) {
  164. int e = dsu.get (x.fi);
  165. if (chkmax (ans, sz[e])) res = r.fi;
  166. }
  167. while (counter--) dsu.rollback ();
  168. }
  169. for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) {
  170. if (chkmax (ans, sz[i * m + j])) res = {goo[i][j], goo[i][j]};
  171. }
  172. cout << ans << '\n' << res.fi << ' ' << res.se << '\n';
  173.  
  174.  
  175.  
  176.  
  177.  
  178.  
  179. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement