fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define mod 1000000007
  4. #define N 100005
  5. #define ll long long
  6. #define p(t) cout<<t;
  7. #define f(i,n) for(i=0;i<n;i++)
  8. #define g(i,n) for(i=1;i<=n;i++)
  9. #define s(x) scanf("%I64d",&x);
  10. #define pb push_back
  11. #define mp make_pair
  12. #define ff first
  13. #define ss second
  14.  
  15. ll r,m,a[N],n,b[N],c[N],pr[N];
  16. vector<ll > v[N],xo[N],su[N];
  17. ll xa,ya,xb,yb;
  18.  
  19. ll check(ll x,ll y,ll x1, ll y1){
  20.     return xo[x1][y1]^xo[x-1][y-1]^xo[x-1][y1]^xo[x1][y-1];
  21. }
  22.  
  23. ll sum(ll x,ll y,ll x1, ll y1){
  24.     return su[x1][y1]-su[x-1][y1]-su[x1][y-1]+su[x-1][y-1];
  25. }
  26.  
  27. void fresh(ll x, ll y, ll x1, ll y1){
  28.     ll g = (x1-x+1)*(y1-y+1);
  29.     if(g>r){
  30.         r=g;
  31.         xa=x;
  32.         ya=y;
  33.         xb=x1;
  34.         yb=y1;
  35.     }
  36. }
  37.  
  38. int main()
  39. {
  40. ios_base::sync_with_stdio(0);
  41. ll k=0,t=0,xq,y=0,l=0,i,j,z,p,q;
  42. cin>>n>>m;
  43. p=0;
  44. if(n>m){
  45.     swap(n,m);
  46.     p=1;
  47. }
  48. ll flag =p;
  49. for(i=0;i<=n;i++){
  50.     v[i].resize(m+1);
  51.     xo[i].resize(m+1);
  52.     su[i].resize(m+1);
  53. }
  54. if(p){
  55.     g(i,m)g(j,n)cin>>v[j][i];
  56. } else {
  57.     g(i,n)g(j,m)cin>>v[i][j];
  58. }
  59. g(i,n)g(j,m){
  60.     xo[i][j]=xo[i-1][j-1]^xo[i][j-1]^xo[i-1][j]^(1<<v[i][j]);
  61.     su[i][j]=su[i-1][j]+su[i][j-1]-su[i-1][j-1]+(v[i][j]>0);
  62. }
  63.  
  64. r=-1;
  65. g(i,n){
  66.     for(j=i;j<=n;j++){
  67.         for(l=0;l<=(1<<10);l++){
  68.             a[l]=-1;
  69.         }
  70.         a[0]=0;
  71.         g(k,m){
  72.             z = check(i,1,j,k);
  73.             if((j-i+1)&1){
  74.                 for(p=0;p<10;p++){
  75.                     q = z^(1<<p);
  76.                     if(a[q]!=-1){
  77.                         if(sum(i,a[q]+1,j,k)>=2){
  78.                         // cout<<i<<" "<<a[q]+1<<" "<<j<<" "<<k<<endl;
  79.                             fresh(i,a[q]+1,j,k);
  80.                         }
  81.                     }
  82.                 }
  83.             }
  84.             if(a[z]!=-1){//cout<<i<<" "<<z<<" "<<a[z]+1<<" "<<j<<" "<<k<<endl;
  85.                     if(sum(i,a[z]+1,j,k)>=1){
  86.                             fresh(i,a[z]+1,j,k);
  87.                         }
  88.             } else{
  89.                 a[z]=k;
  90.             }
  91.         }
  92.     } 
  93. }
  94. if(flag){
  95. 	swap(xa,ya); swap(xb,yb);
  96. }
  97. xa--; ya--;  xb--; yb--;
  98. if(r==-1){
  99. r=1; xa=ya=xb=yb=0;
  100. }
  101. cout<<r<<" "<<xa<<" "<<ya<<" "<<xb<<" "<<yb;
  102. return 0;
  103. }
  104.  
Success #stdin #stdout 0s 25400KB
comments (?)
stdin
copy 
5 5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
stdout
copy 
1 0 0 0 0
https://ideone.com/ONPQF2
language:
C++14 (clang 8.0)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!