Cod sursa(job #2910306)

Utilizator euyoTukanul euyo Data 19 iunie 2022 09:21:19
Problema Zone Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.5 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin( "zone.in" );
ofstream fout( "zone.out" );

using ll = long long;

const int DIM = 520;
const int NZ = 9; 

ll sum[NZ + 1];
int a[DIM][DIM];

ll S[DIM][DIM];

int n;
int l1 = 1e9, c1 = 1e9, l2 = 1e9, c2 = 1e9;

int bsl( ll val, int c ) {
  int st = 0, dr = n;

  while ( dr - st > 1 ) {
	int mid = (st + dr) / 2;
	if ( S[mid][c] < val ) {
	  st = mid;
	} else {
	  dr = mid;
	}
  }
  if ( S[st][c] == val ) return st;
  if ( S[dr][c] == val ) return dr;
  return -1;
}
int bsc( ll val, int l ) {
  int st = 0, dr = n;

  while ( dr - st > 1 ) {
	int mid = (st + dr) / 2;
	if ( S[l][mid] < val ) {
	  st = mid;
	} else {
	  dr = mid;
	}
  }
  if ( S[l][st] == val ) return st;
  if ( S[l][dr] == val ) return dr;
  return -1;
}

void solve( int x, int y, int z, int zl1 ) {
  // x = zona 1 , y = zona 2, z = zona 4
  int zc1 = bsc( sum[x], zl1 );
  if ( zc1 == -1 ) return;
  int zl2 = bsl( sum[x] + sum[z], zc1 );
  int zc2 = bsc( sum[x] + sum[y], zl1 ); 
  if ( zl1 == -1 || zl2 == -1 || zc1 == -1 || zc2 == -1 ) return;
  vector<int> q(NZ + 1);
  q[1] = S[zl1][zc1];
  q[2] = S[zl1][zc2] - S[zl1][zc1];
  q[3] = S[zl1][n] - S[zl1][zc2];
  q[4] = S[zl2][zc1] - S[zl1][zc1];
  q[5] = S[zl2][zc2] - q[1] - q[2] - q[4];
  q[6] = S[zl2][n] - q[1] - q[2] - q[3] - q[4] - q[5];
  q[7] = S[n][zc1] - S[zl2][zc1];
  q[8] = S[n][zc2] - q[1] - q[2] - q[4] - q[5] - q[7];
  q[9] = S[n][n] - q[1] - q[2] - q[3] - q[4] - q[5] - q[6] - q[7] - q[8];
  sort( q.begin(), q.end() );
  for ( int i = 1; i <= NZ; ++i ) {
	if ( q[i] != sum[i] ) return;
  }
  if ( l1 > zl1 ) {
	l1 = zl1, l2 = zl2, c1 = zc1, c2 = zc2;
  } else if ( l1 == zl1 ) {
	if ( c1 > zc1 ) {
	  l1 = zl1, l2 = zl2, c1 = zc1, c2 = zc2;
	} else if ( c1 == zc1 ) {
	  if ( l2 > zl2 ) {
		l1 = zl1, l2 = zl2, c1 = zc1, c2 = zc2;
	  } else if ( l2 == zl2 ) {
		if ( c2 > zc2 ) {
		  l1 = zl1, l2 = zl2, c1 = zc1, c2 = zc2;
		}
	  }
	}
  }
}

int main() {
  fin >> n;
  for ( int i = 1; i <= NZ; ++i ) fin >> sum[i];
  sort(sum + 1, sum + NZ + 1);
  for ( int i = 1; i <= n; ++i ) {
	for ( int j = 1; j <= n; ++j ) {
	  fin >> a[i][j];
	  S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + a[i][j];
	}
  }
  for ( int i = 1; i <= n; ++i ) {
	for ( int x = 1; x <= NZ; ++x ) {
	  for ( int y = 1; y <= NZ; ++y ) {
		if ( x == y ) continue;
		for ( int z = 1; z <= NZ; ++z ) {
		  if ( x == z || y == z ) continue; 
		  solve(x, y, z, i);
		}
	  }
	}
  }
  fout << l1 << " " << l2 << " " << c1 << " " << c2 << "\n";
  fin.close();
  fout.close();
  return 0;
}