Submission #421163

#	Time	Username	Problem	Language	Result	Execution time	Memory
421163		rama_pang	Izvanzemaljci (COI21_izvanzemaljci)	C++17	100 / 100	1584 ms	25448 KiB

izvanzemaljci

#include <bits/stdc++.h>
using namespace std;

using lint = long long;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N, K;
  cin >> N >> K;

  vector<lint> X(N), Y(N);
  for (int i = 0; i < N; i++) {
    cin >> X[i] >> Y[i];
  }

  long long answerScore = 1e18;
  vector<array<lint, 4>> answer;

  for (int rot = 0; rot < 4; rot++) {
    vector<int> sortByX(N);
    vector<int> sortByY(N);
    iota(begin(sortByX), end(sortByX), 0);
    iota(begin(sortByY), end(sortByY), 0);
    sort(begin(sortByX), end(sortByX), [&](int i, int j) {
      return pair(X[i], Y[i]) < pair(X[j], Y[j]);
    });
    sort(begin(sortByY), end(sortByY), [&](int i, int j) {
      return pair(Y[i], X[i]) < pair(Y[j], X[j]);
    });
    vector<int> posInSortByX(N);
    vector<int> posInSortByY(N);
    for (int i = 0; i < N; i++) {
      posInSortByX[sortByX[i]] = i;
      posInSortByY[sortByY[i]] = i;
    }

    const auto CountingSort = [&](vector<int> &a, const vector<int> &sorted, const vector<int> &pos) {
      static vector<int> res(N);
      fill(begin(res), end(res), 0);
      for (auto i : a) {
        res[pos[i]] = 1;
      }
      a.clear();
      for (int i = 0; i < N; i++) {
        if (res[i]) {
          a.emplace_back(sorted[i]);
        }
      }
    };

    vector<array<lint, 3>> ans;
    const auto SolveK1 = [&](vector<int> alive, lint boundLftX, lint boundRgtX, lint boundLftY, lint boundRgtY, int trace) -> lint {
      if (alive.empty()) return 0;
      lint minX = +2e9;
      lint maxX = -2e9;
      lint minY = +2e9;
      lint maxY = -2e9;
      for (auto i : alive) {
        minX = min(minX, X[i]);
        maxX = max(maxX, X[i]);
        minY = min(minY, Y[i]);
        maxY = max(maxY, Y[i]);
      }

      lint len = max({1ll, maxX - minX, maxY - minY});
      if (boundRgtX - boundLftX < len) return 1e18;
      if (boundRgtY - boundLftY < len) return 1e18;

      if (!trace) {
        return len;
      }

      for (auto x : {boundLftX, minX, maxX - len, boundRgtX - len}) if (-3e9 <= x && x <= 3e9) {
        if (boundLftX <= x && x + len <= boundRgtX) {
          for (auto y : {boundLftY, minY, maxY - len, boundRgtY - len}) if (-3e9 <= y && y <= 3e9) {
            if (boundLftY <= y && y + len <= boundRgtY) {
              bool bad = false;
              for (auto i : alive) {
                if (x <= X[i] && X[i] <= x + len && y <= Y[i] && Y[i] <= y + len) {

                } else {
                  bad = true;
                  break;
                }
              }
              if (!bad) {
                ans.push_back({x, y, len});
                return len;
              }
            }
          }
        }
      }
      assert(false);
      return 1e18;
    };

    map<tuple<vector<int>, int, lint>, lint> memoK2;
    const auto SolveK2 = [&](vector<int> alive, int vert, lint boundLftX, int trace) -> lint {
      if (alive.empty()) return 0;
      if (auto it = memoK2.find({alive, vert, boundLftX}); trace == 0 && it != end(memoK2)) {
        return it->second;
      }

      lint res = SolveK1(alive, boundLftX, 1e18, -1e18, 1e18, 0);

      if (!vert) {
        CountingSort(alive, sortByY, posInSortByY);
      } else {
        CountingSort(alive, sortByX, posInSortByX);
      }

      static vector<lint> prefMinX(N);
      static vector<lint> prefMaxX(N);
      static vector<lint> prefMinY(N);
      static vector<lint> prefMaxY(N);

      static vector<lint> suffMinX(N);
      static vector<lint> suffMaxX(N);
      static vector<lint> suffMinY(N);
      static vector<lint> suffMaxY(N);

      for (int i = 0; i < int(alive.size()); i++) {
        int id = alive[i];
        prefMinX[i] = prefMaxX[i] = X[id];
        prefMinY[i] = prefMaxY[i] = Y[id];
        suffMinX[i] = suffMaxX[i] = X[id];
        suffMinY[i] = suffMaxY[i] = Y[id];
      }
      for (int i = 1; i < int(alive.size()); i++) {
        prefMinX[i] = min(prefMinX[i], prefMinX[i - 1]);
        prefMaxX[i] = max(prefMaxX[i], prefMaxX[i - 1]);
        prefMinY[i] = min(prefMinY[i], prefMinY[i - 1]);
        prefMaxY[i] = max(prefMaxY[i], prefMaxY[i - 1]);
      }
      for (int i = int(alive.size()) - 2; i >= 0; i--) {
        suffMinX[i] = min(suffMinX[i], suffMinX[i + 1]);
        suffMaxX[i] = max(suffMaxX[i], suffMaxX[i + 1]);
        suffMinY[i] = min(suffMinY[i], suffMinY[i + 1]);
        suffMaxY[i] = max(suffMaxY[i], suffMaxY[i + 1]);
      }

      const auto CalcPref = [&](int i) -> lint {
        if (i < 0 || i >= int(alive.size())) return 0;
        return max(prefMaxX[i] - prefMinX[i], prefMaxY[i] - prefMinY[i]);
      };

      const auto CalcSuff = [&](int i) -> lint {
        if (i < 0 || i >= int(alive.size())) return 0;
        return max(suffMaxX[i] - suffMinX[i], suffMaxY[i] - suffMinY[i]);
      };

      if (vert == 0) {
        for (int i = 0; i < int(alive.size()); i++) {
          if (!(i + 1 == int(alive.size()) || Y[alive[i + 1]] != Y[alive[i]])) {
            continue;
          }
          res = min(res, max(CalcPref(i), CalcSuff(i + 1)));
        }

        if (res == 1e18) {
          return memoK2[{alive, vert, boundLftX}] = res;
        }

        vector<int> pref;
        vector<int> suff = alive;
        reverse(begin(suff), end(suff));
        for (int i = 0; i < int(alive.size()); i++) {
          pref.emplace_back(alive[i]);
          suff.pop_back();
          if (!(i + 1 == int(alive.size()) || Y[alive[i + 1]] != Y[alive[i]])) {
            continue;
          }
          if (res == max(CalcPref(i), CalcSuff(i + 1))) {
            SolveK1(pref, boundLftX, 1e18, -1e18, Y[alive[i]], trace);
            SolveK1(suff, boundLftX, 1e18, Y[alive[i]] + 1, 1e18, trace);
            return memoK2[{alive, vert, boundLftX}] = res;
          }
        }
      } else {
        for (int i = 0; i < int(alive.size()); i++) {
          if (!(i + 1 == int(alive.size()) || X[alive[i + 1]] != X[alive[i]])) {
            continue;
          }
          lint len = CalcPref(i);
          lint upTo = (i + 1 == int(alive.size())) ? 1e18 : (X[alive[i + 1]] - 1);
          if (upTo - max(boundLftX, prefMinX[i]) < len) continue;
          res = min(res, max(CalcPref(i), CalcSuff(i + 1)));
        }

        if (res == 1e18) {
          return memoK2[{alive, vert, boundLftX}] = res;
        }

        vector<int> pref;
        vector<int> suff = alive;
        reverse(begin(suff), end(suff));
        for (int i = 0; i < int(alive.size()); i++) {
          pref.emplace_back(alive[i]);
          suff.pop_back();
          if (!(i + 1 == int(alive.size()) || X[alive[i + 1]] != X[alive[i]])) {
            continue;
          }
          lint len = CalcPref(i);
          lint upTo = (i + 1 == int(alive.size())) ? 1e18 : (X[alive[i + 1]] - 1);
          if (upTo - max(boundLftX, prefMinX[i]) < len) continue;
          if (res == max(CalcPref(i), CalcSuff(i + 1))) {
            SolveK1(pref, boundLftX, upTo, -1e18, 1e18, trace);
            SolveK1(suff, upTo + 1, 1e18, -1e18, 1e18, trace);
            return memoK2[{alive, vert, boundLftX}] = res;
          }
        }
      }

      if (res == SolveK1(alive, boundLftX, 1e18, -1e18, 1e18, 0)) {
        return memoK2[{alive, vert, boundLftX}] = SolveK1(alive, boundLftX, 1e18, -1e18, 1e18, trace);
      }

      return memoK2[{alive, vert, boundLftX}] = 1e18;
    };

    const auto SolveK3 = [&](vector<int> alive, int trace) -> lint {
      lint res = 1e18;
      res = min(res, SolveK2(alive, 0, -1e18, 0));
      res = min(res, SolveK2(alive, 1, +1e18, 0));

      CountingSort(alive, sortByX, posInSortByX);

      static vector<lint> prefMinX(N);
      static vector<lint> prefMaxX(N);
      static vector<lint> prefMinY(N);
      static vector<lint> prefMaxY(N);

      for (int i = 0; i < int(alive.size()); i++) {
        int id = alive[i];
        prefMinX[i] = prefMaxX[i] = X[id];
        prefMinY[i] = prefMaxY[i] = Y[id];
      }
      for (int i = 1; i < int(alive.size()); i++) {
        prefMinX[i] = min(prefMinX[i], prefMinX[i - 1]);
        prefMaxX[i] = max(prefMaxX[i], prefMaxX[i - 1]);
        prefMinY[i] = min(prefMinY[i], prefMinY[i - 1]);
        prefMaxY[i] = max(prefMaxY[i], prefMaxY[i - 1]);
      }

      const auto CalcPref = [&](int i) -> lint {
        if (i < 0 || i >= int(alive.size())) return 0;
        return max(prefMaxX[i] - prefMinX[i], prefMaxY[i] - prefMinY[i]);
      };

      vector<lint> coordX = X;
      sort(begin(coordX), end(coordX));
      coordX.resize(unique(begin(coordX), end(coordX)) - begin(coordX));

      const auto Check = [&](lint maxD) -> pair<int, bool> {
        int ok = -1;
        for (int i = 0; i < int(alive.size()); i++) {
          if (!(i + 1 == int(alive.size()) || X[alive[i + 1]] != X[alive[i]])) {
            continue;
          }
          if (CalcPref(i) <= maxD) {
            ok = i;
          }
        }

        vector<int> other;
        for (int i = ok + 1; i < int(alive.size()); i++) {
          other.emplace_back(alive[i]);
        }

        return {ok, min(SolveK2(other, 0, ok == -1 ? -1e18 : (X[alive[ok]] + 1), 0),
                        SolveK2(other, 1, ok == -1 ? -1e18 : (X[alive[ok]] + 1), 0)) <= maxD};
      };

      lint lo = 1, hi = 2e9;
      while (lo < hi) {
        lint md = (lo + hi) / 2;
        if (Check(md).second) {
          hi = md;
        } else {
          lo = md + 1;
        }
      }

      int cand = Check(lo).first;
      vector<int> suff = alive;
      reverse(begin(suff), end(suff));
      for (int i = 0; i < int(alive.size()); i++) {
        suff.pop_back();
        if (!(i + 1 == int(alive.size()) || X[alive[i + 1]] != X[alive[i]])) {
          continue;
        }
        if (i != cand) continue;
        res = min(res, max(CalcPref(i), SolveK2(suff, 0, X[alive[i]] + 1, 0)));
        res = min(res, max(CalcPref(i), SolveK2(suff, 1, X[alive[i]] + 1, 0)));
      }

      if (res == 1e18) {
        return res;
      }

      suff = alive;
      vector<int> pref;
      reverse(begin(suff), end(suff));
      for (int i = 0; i < int(alive.size()); i++) {
        pref.emplace_back(alive[i]);
        suff.pop_back();
        if (!(i + 1 == int(alive.size()) || X[alive[i + 1]] != X[alive[i]])) {
          continue;
        }
        if (i != cand) continue;
        if (res == max(CalcPref(i), SolveK2(suff, 0, X[alive[i]] + 1, 0))) {
          SolveK1(pref, -1e18, X[alive[i]], -1e18, 1e18, trace);
          SolveK2(suff, 0, X[alive[i]] + 1, trace);
          return res;
        }
        if (res == max(CalcPref(i), SolveK2(suff, 1, X[alive[i]] + 1, 0))) {
          SolveK1(pref, -1e18, X[alive[i]], -1e18, 1e18, trace);
          SolveK2(suff, 1, X[alive[i]] + 1, trace);
          return res;
        }
      }

      if (res == SolveK2(alive, 0, -1e18, 0)) {
        return SolveK2(alive, 0, -1e18, trace);
      }

      if (res == SolveK2(alive, 1, -1e18, 0)) {
        return SolveK2(alive, 1, -1e18, trace);
      }

      return 1e18;
    };

    const auto Solve = [&](int K, int trace) -> lint {
      vector<int> alive(N);
      iota(begin(alive), end(alive), 0);
      if (K == 1) {
        ans.clear();
        return SolveK1(alive, -1e18, 1e18, -1e18, 1e18, trace);
      } else if (K == 2) {
        ans.clear();
        lint res1 = SolveK2(alive, 0, -1e18, trace);
        auto ans1 = ans;
        ans.clear();
        lint res2 = SolveK2(alive, 1, -1e18, trace);
        auto ans2 = ans;
        if (res1 < res2) {
          ans = ans1;
          return res1;
        } else {
          ans = ans2;
          return res2;
        }
      } else if (K == 3) {
        ans.clear();
        return SolveK3(alive, trace);
      } else {
        assert(false);
        return -1;
      }
    };

    lint res = Solve(K, 1);
    if (res < answerScore) {
      answerScore = res;
      answer.clear();
      for (auto &a : ans) {
        answer.push_back({a[0], a[1], a[0] + a[2], a[1] + a[2]});
      }
    }

    for (int i = 0; i < N; i++) {
      swap(X[i], Y[i]); Y[i] *= -1;
    }
    for (int i = 0; i < int(answer.size()); i++) {
      swap(answer[i][0], answer[i][1]); answer[i][1] *= -1;
      swap(answer[i][2], answer[i][3]); answer[i][3] *= -1;
    }
  }

  vector<array<lint, 3>> ans;
  for (auto a : answer) {
    if (a[0] > a[2]) swap(a[0], a[2]);
    if (a[1] > a[3]) swap(a[1], a[3]);
    assert(a[2] - a[0] == a[3] - a[1]);
    ans.push_back({a[0], a[1], a[2] - a[0]});
  }

  int it = 0;
  while (int(ans.size()) < K) {
    ans.push_back({lint(-3e9 + 2 * it), lint(3e9), 1});
    it++;
  }

  const auto ValidAnswer = [&](vector<array<lint, 3>> sq) {
    assert(int(sq.size()) <= K);
    for (int i = 0; i < int(sq.size()); i++) {
      for (int j = 0; j < int(sq.size()); j++) if (i != j) {
        for (auto x : {sq[j][0], sq[j][0] + sq[j][2]}) {
          for (auto y : {sq[j][1], sq[j][1] + sq[j][2]}) {
            lint minX = sq[i][0];
            lint maxX = sq[i][0] + sq[i][2];
            lint minY = sq[i][1];
            lint maxY = sq[i][1] + sq[i][2];
            if (minX <= x && x <= maxX && minY <= y && y <= maxY) {
              return false;
            }
          }
        }
      }
    }
    for (int i = 0; i < N; i++) {
      bool found = false;
      for (auto [x, y, l] : sq) {
        if (x <= X[i] && X[i] <= x + l && y <= Y[i] && Y[i] <= y + l) {
          found = true;
          break;
        }
      }
      if (!found) {
        return false;
      }
    }
    return true;
  };

  assert(ValidAnswer(ans));
  for (int i = 0; i < K; i++) {
    cout << ans[i][0] << ' ' << ans[i][1] << ' ' << ans[i][2] << '\n';
  }
  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 21 / 21
• Subtask 3: 12 / 12
• Subtask 4: 30 / 30
• Subtask 5: 32 / 32