Guest User

Untitled

a guest
Aug 17th, 2015
373
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.19 KB | None | 0 0
  1. /*
  2. */
  3.  
  4. //#pragma comment(linker, "/STACK:16777216")
  5. #include <fstream>
  6. #include <iostream>
  7. #include <string>
  8. #include <complex>
  9. #include <math.h>
  10. #include <set>
  11. #include <vector>
  12. #include <map>
  13. #include <queue>
  14. #include <stdio.h>
  15. #include <stack>
  16. #include <algorithm>
  17. #include <list>
  18. #include <ctime>
  19. #include <memory.h>
  20. #include <ctime>
  21.  
  22. #define y0 sdkfaslhagaklsldk
  23. #define y1 aasdfasdfasdf
  24. #define yn askfhwqriuperikldjk
  25. #define j1 assdgsdgasghsf
  26. #define tm sdfjahlfasfh
  27. #define lr asgasgash
  28.  
  29. #define eps 1e-9
  30. #define M_PI 3.141592653589793
  31. #define bs 1000000007
  32. #define bsize 512
  33.  
  34. using namespace std;
  35.  
  36. long long pw[1<<20];
  37. int ar[2050][2050];
  38. long long su[2050][2050],sd[2050][2050],sl[2050][2050],sr[2050][2050];
  39. int ans,ai,aj;
  40. int l,r;
  41. int n,m;
  42.  
  43. bool check(int a,int b,int side)
  44. {
  45. long long val=su[a][b]-su[a-side][b];
  46. val*=pw[10000-(a-side)];
  47. long long val1=sr[a][b]-sr[a][b+side];
  48. val1*=pw[10000-(m-(b+side-1))];
  49. if (val1!=val)
  50. return false;
  51. val1=sd[a][b]-sd[a+side][b];
  52. val1*=pw[10000-(n-(a+side-1))];
  53. if (val1!=val)
  54. return false;
  55. val1=sl[a][b]-sl[a][b-side];
  56. val1*=pw[10000-(b-side)];
  57. if (val1!=val)
  58. return false;
  59. return true;
  60. }
  61.  
  62. int main(){
  63. //freopen("blind.in","r",stdin);
  64. //freopen("blind.out","w",stdout);
  65. //freopen("F:/in.txt","r",stdin);
  66. //freopen("F:/output.txt","w",stdout);
  67. //ios_base::sync_with_stdio(0);
  68. //cin.tie(0);
  69.  
  70. pw[0]=1;
  71. for (int i=1;i<=10000;i++)
  72. pw[i]=pw[i-1]*173;
  73.  
  74. cin>>n>>m;
  75. for (int i=1;i<=n;i++)
  76. for (int j=1;j<=m;j++)
  77. {
  78. scanf("%d",&ar[i][j]);
  79. }
  80.  
  81. for (int i=1;i<=n;i++)
  82. for (int j=1;j<=m;j++)
  83. {
  84. su[i][j]=su[i-1][j]+ar[i][j]*pw[i];
  85. sl[i][j]=sl[i][j-1]+ar[i][j]*pw[j];
  86. }
  87.  
  88. for (int i=n;i;--i)
  89. for (int j=m;j;--j)
  90. {
  91. sd[i][j]=sd[i+1][j]+ar[i][j]*pw[n-i+1];
  92. sr[i][j]=sr[i][j+1]+ar[i][j]*pw[m-j+1];
  93. }
  94.  
  95. ans=0;
  96.  
  97. for (int i=1;i<=n;i++)
  98. for (int j=1;j<=m;j++)
  99. {
  100. l=ans;
  101. r=min(i,j);
  102. r=min(r,n-i+1);
  103. r=min(r,m-j+1);
  104. while (l<r)
  105. {
  106. int mid=l+r+1;
  107. mid/=2;
  108. if (check(i,j,mid))
  109.  
  110. l=mid;
  111. else
  112. r=mid-1;
  113. }
  114. if (l>ans)
  115. {
  116. ans=l;
  117. ai=i;
  118. aj=j;
  119. }
  120. }
  121.  
  122. cout<<ans-1<<" "<<ai<<" "<<aj<<endl;
  123.  
  124. //cin.get();cin.get();
  125. return 0;}
Advertisement
Add Comment
Please, Sign In to add comment