Cod sursa(job #2774502)

Utilizator racsosabeVictor Racso Galvan Oyola racsosabe Data 11 septembrie 2021 19:16:49
Problema Zone Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.83 kb
#include <bits/stdc++.h>
using namespace std;

void setIO(string name, bool input = true, bool output = true){
  string inputname = name + ".in";
  string outputname = name + ".out";
  if(input) freopen(inputname.c_str(), "r", stdin);
  if(output) freopen(outputname.c_str(), "w", stdout);
}

const int N = 512 + 5;

int n;
int m;
long long a[N][N];
vector<long long> values;

long long query(int x1, int y1, int x2, int y2){
  return a[x2][y2] + a[x1 - 1][y1 - 1] - a[x1 - 1][y2] - a[x2][y1 - 1];
}

bool check(int l1, int c1, int l2, int c2){
  vector<long long> here;
  here.emplace_back(query(1, 1, l1, c1));
  here.emplace_back(query(1, c1 + 1, l1, c2));
  here.emplace_back(query(1, c2 + 1, l1, n));
  here.emplace_back(query(l1 + 1, 1, l2, c1));
  here.emplace_back(query(l1 + 1, c1 + 1, l2, c2));
  here.emplace_back(query(l1 + 1, c2 + 1, l2, n));
  here.emplace_back(query(l2 + 1, 1, n, c1));
  here.emplace_back(query(l2 + 1, c1 + 1, n, c2));
  here.emplace_back(query(l2 + 1, c2 + 1, n, n));
  sort(here.begin(), here.end());
  return here == values;
}

tuple<int, int, int, int> get_answer(int l1, int l2){
  tuple<int, int, int, int> res = make_tuple(-1, -1, -1, -1);
  int lo = 1, hi;
  for(int i = 0; i < values.size(); i++){
    hi = n - 2;
    while(lo < hi){
      int mi = lo + (hi - lo) / 2;
      if(query(1, 1, l1, mi) < values[i]) lo = mi + 1;
      else hi = mi;
    }
    if(query(1, 1, l1, lo) != values[i]) continue;
    int hi2;
    int lo2 = lo + 1;
    for(int j = 0; j < values.size(); j++){
      if(i == j) continue;
      hi2 = n - 1;
      while(lo2 < hi2){
        int mi = lo2 + (hi2 - lo2) / 2;
        if(query(1, lo + 1, l1, mi) < values[j]) lo2 = mi + 1;
        else hi2 = mi;
      }
      if(query(1, lo + 1, l1, lo2) != values[j]) continue;
      if(check(l1, lo, l2, lo2)){
        tuple<int, int, int, int> cur = make_tuple(l1, lo, l2, lo2);
        if(get<0>(res) == -1 or cur < res) res = cur;
      }
    }
  }
  return res;
}

void solve(){
  sort(values.begin(), values.end());
  tuple<int, int, int, int> res = make_tuple(-1, -1, -1, -1);
  for(int l1 = 1; l1 <= n; l1++){
    for(int l2 = l1 + 1; l2 < n; l2++){
      tuple<int, int, int, int> cur = get_answer(l1, l2);
      if(get<0>(cur) == -1) continue;
      if(get<0>(res) == -1 or cur < res) res = cur;
    }
  }
  printf("%d %d %d %d\n", get<0>(res), get<2>(res), get<1>(res), get<3>(res));
}

int main(){
  setIO("zone");
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  scanf("%d", &n);
  for(int i = 0; i < 9; i++){
    long long x;
    scanf("%lld", &x);
    values.emplace_back(x);
  }
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
      scanf("%lld", &a[i][j]);
      a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
    }
  }
  solve();
  return 0;
}