Submission #420897

#	Time	Username	Problem	Language	Result	Execution time	Memory
420897		rama_pang	Izvanzemaljci (COI21_izvanzemaljci)	C++17	26 / 100	569 ms	12504 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];
  }

  // There is a vertical or horizontal line which divides K = 3 -> {1, 2}.
  // Binary search the answer L. If cuts are shaped like (|-), then we
  // can greedily take big left part. If cuts are shaped like (| |), we
  // brute force middle (as we can greedily take middle), precompute left part
  // and right part.
  //
  // This takes O(N log MAX).

  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 = [&](lint L, const vector<int> &alive, int config, int trace) {
    if (alive.empty()) return true;
    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]);
    }
    if (maxX - minX <= L && maxY - minY <= L) {
      lint len = max({1ll, maxX - minX, maxY - minY});
      if (trace == 1 && config == 0) ans.push_back({minX, minY, len});
      if (trace == 1 && config == 1) ans.push_back({maxX - len, minY, len});
      if (trace == 1 && config == 2) ans.push_back({maxX - len, maxY - len, len});
      if (trace == 1 && config == 3) ans.push_back({minX, maxY - len, len});
      return true;
    }
    return false;
  };

  const auto SolveK2 = [&](int L, vector<int> alive, int vert, int trace) {
    if (alive.empty()) return true;

    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 >= alive.size()) return 0;
      return max(prefMaxX[i] - prefMinX[i], prefMaxY[i] - prefMinY[i]);
    };
    const auto CalcSuff = [&](int i) -> lint {
      if (i < 0 || i >= alive.size()) return 0;
      return max(suffMaxX[i] - suffMinX[i], suffMaxY[i] - suffMinY[i]);
    };

    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 == alive.size() ||
           (vert == 0 && Y[alive[i + 1]] != Y[alive[i]]) ||
           (vert == 1 && X[alive[i + 1]] != X[alive[i]]))) {
        continue;
      }

      if (CalcPref(i) <= L && CalcSuff(i + 1) <= L) {
        assert(SolveK1(L, pref, 2, trace));
        assert(SolveK1(L, suff, 0, trace));
        return true;
      }
    }
    return false;
  };

  const auto SolveK3 = [&](lint L, vector<int> alive, int vert, int trace) {
    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 >= alive.size()) return 0;
      return max(prefMaxX[i] - prefMinX[i], prefMaxY[i] - prefMinY[i]);
    };
    const auto CalcSuff = [&](int i) -> lint {
      if (i < 0 || i >= alive.size()) return 0;
      return max(suffMaxX[i] - suffMinX[i], suffMaxY[i] - suffMinY[i]);
    };

    // Configuration: |-
    int last = -1;
    for (int i = 0; i < int(alive.size()); i++) {
      if (!(i + 1 == alive.size() ||
           (vert == 0 && Y[alive[i + 1]] != Y[alive[i]]) ||
           (vert == 1 && X[alive[i + 1]] != X[alive[i]]))) {
        continue;
      }
      if (CalcPref(i) <= L) {
        last = i;
      }
    }
    if (last != -1) {
      vector<int> other;
      for (int i = last + 1; i < int(alive.size()); i++) {
        other.emplace_back(alive[i]);
      }
      if (SolveK2(L, other, 1 - vert, trace)) {
        if (trace) {
          other.clear();
          for (int i = 0; i <= last; i++) {
            other.emplace_back(alive[i]);
          }
          SolveK1(L, other, 2, trace);
        }
        return true;
      }
    }

    // Configuration: -|
    last = -1;
    for (int i = int(alive.size()) - 1; i >= 0; i--) {
      if (!(i == 0 ||
           (vert == 0 && Y[alive[i - 1]] != Y[alive[i]]) ||
           (vert == 1 && X[alive[i - 1]] != X[alive[i]]))) {
        continue;
      }
      if (CalcSuff(i) <= L) {
        last = i;
      }
    }
    if (last != -1) {
      vector<int> other;
      for (int i = 0; i < last; i++) {
        other.emplace_back(alive[i]);
      }
      if (SolveK2(L, other, 1 - vert, trace)) {
        if (trace) {
          other.clear();
          for (int i = last; i < int(alive.size()); i++) {
            other.emplace_back(alive[i]);
          }
          SolveK1(L, other, 0, trace);
        }
        return true;
      }
    }

    // Configuration: | |

    for (int i = 0; i < int(alive.size()); i++) {
      lint minX = X[alive[i]];
      lint maxX = X[alive[i]];
      lint minY = Y[alive[i]];
      lint maxY = Y[alive[i]];

      if (!(i == 0 ||
           (vert == 0 && Y[alive[i - 1]] != Y[alive[i]]) ||
           (vert == 1 && X[alive[i - 1]] != X[alive[i]]))) {
        continue;
      }

      for (int j = i; j < int(alive.size()); j++) {
        minX = min(minX, X[alive[j]]);
        maxX = max(maxX, X[alive[j]]);
        minY = min(minY, Y[alive[j]]);
        maxY = max(maxY, Y[alive[j]]);

        if (!(j + 1 == alive.size() ||
            (vert == 0 && Y[alive[j + 1]] != Y[alive[j]]) ||
            (vert == 1 && X[alive[j + 1]] != X[alive[j]]))) {
          continue;
        }

        if ((vert == 0 && maxX - minX <= maxY - minY && maxY - minY <= L) ||
            (vert == 1 && maxY - minY <= maxX - minX && maxX - minX <= L)) {
          if (CalcPref(i - 1) <= L && CalcSuff(j + 1) <= L) {
            if (trace) {
              vector<int> a, b, c;
              for (int x = 0; x < int(alive.size()); x++) {
                if (x < i) a.emplace_back(alive[x]);
                else if (x > j) c.emplace_back(alive[x]);
                else b.emplace_back(alive[x]);
              }
              assert(SolveK1(L, a, 2, trace));
              assert(SolveK1(L, b, 0, trace));
              assert(SolveK1(L, c, 0, trace));
            }
            return true;
          }
        }
      }
    }
    return false;

    // deque<pair<lint, int>> minQue;
    // deque<pair<lint, int>> maxQue;

    // const auto CanInsert = [&](int id) {
    //   if (minQue.empty() || maxQue.empty()) return true;
    //   lint val;
    //   if (vert == 0) {
    //     // horizontal, keep minX and maxX
    //     val = X[id];
    //   } else {
    //     // vertical, keep minY and maxY
    //     val = Y[id];
    //   }
    //   if (max(maxQue.front().first, val) - min(minQue.front().first, val) <= L) {
    //     return true;
    //   }
    // };

    // for (int i = 0, j = -1; i < int(alive.size()); i++) {
    //   while (j + 1 < int(alive.size()) &&
    //          (vert == 0 ? (Y[alive[j + 1]] - Y[alive[i]]) : (X[alive[j + 1]] - X[alive[i]])) <= L &&
    //          CanInsert(alive[j + 1])) {
    //     Insert(alive[j++]);
    //   }
    //   if (CalcPref(i - 1) <= L && CalcSuff(j + 1) <= L) {

    //   }
    //   Erase(alive[i]);
    // }



  };

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

  lint lo = 1;
  lint hi = 2e9;
  while (lo < hi) {
    lint md = (lo + hi) / 2;
    if (Solve(K, md, 0)) {
      hi = md;
    } else {
      lo = md + 1;
    }
  }

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

  const auto NotIntersect = [&](vector<array<lint, 3>> sq) {
    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;
            }
          }
        }
      }
    }
    return true;
  };

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

Compilation message (stderr)

izvanzemaljci.cpp: In lambda function:
izvanzemaljci.cpp:121:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |       if (i < 0 || i >= alive.size()) return 0;
      |                    ~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp: In lambda function:
izvanzemaljci.cpp:125:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |       if (i < 0 || i >= alive.size()) return 0;
      |                    ~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp: In lambda function:
izvanzemaljci.cpp:136:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |       if (!(i + 1 == alive.size() ||
      |             ~~~~~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp: In lambda function:
izvanzemaljci.cpp:189:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  189 |       if (i < 0 || i >= alive.size()) return 0;
      |                    ~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp: In lambda function:
izvanzemaljci.cpp:193:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  193 |       if (i < 0 || i >= alive.size()) return 0;
      |                    ~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp: In lambda function:
izvanzemaljci.cpp:200:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  200 |       if (!(i + 1 == alive.size() ||
      |             ~~~~~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp:275:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  275 |         if (!(j + 1 == alive.size() ||
      |               ~~~~~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp: In function 'int main()':
izvanzemaljci.cpp:377:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  377 |   while (ans.size() < K) {
      |          ~~~~~~~~~~~^~~

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