Cod sursa(job #2774511)

Utilizator racsosabeVictor Racso Galvan Oyola racsosabe Data 11 septembrie 2021 19:24:44
Problema Zone Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.58 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){
  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)){
        return make_tuple(l1, lo, l2, lo2);
      }
    }
  }
  return make_tuple(-1, -1, -1, -1);
}

void solve(){
  sort(values.begin(), values.end());
  for(int l1 = 1; l1 + 1 < 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;
      printf("%d %d %d %d\n", get<0>(cur), get<2>(cur), get<1>(cur), get<3>(cur));
      return;
    }
  }
}

int main(){
  setIO("zone");
  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++){
      int x;
      scanf("%d", &x);
      a[i][j] = x + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
    }
  }
  solve();
  return 0;
}