oj.uz

Submission #421163

# Submission time Handle Problem Language Result Execution time Memory
421163 2021-06-08T19:39:19 Z rama_pang Izvanzemaljci (COI21_izvanzemaljci) C++17
100 / 100
 1584 ms 25448 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 154 ms 4224 KB Output is correct
8 Correct 153 ms 4188 KB Output is correct
9 Correct 153 ms 4196 KB Output is correct
10 Correct 163 ms 4380 KB Output is correct
11 Correct 163 ms 4208 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 235 ms 12252 KB Output is correct
11 Correct 221 ms 12240 KB Output is correct
12 Correct 221 ms 12428 KB Output is correct
13 Correct 219 ms 12660 KB Output is correct
14 Correct 219 ms 13028 KB Output is correct
15 Correct 223 ms 12612 KB Output is correct
16 Correct 234 ms 13016 KB Output is correct
17 Correct 201 ms 11704 KB Output is correct
18 Correct 206 ms 11120 KB Output is correct
19 Correct 173 ms 10416 KB Output is correct
20 Correct 187 ms 10876 KB Output is correct
21 Correct 244 ms 12980 KB Output is correct
22 Correct 224 ms 12512 KB Output is correct
23 Correct 223 ms 12944 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 284 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 204 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 460 KB Output is correct
2 Correct 10 ms 460 KB Output is correct
3 Correct 10 ms 460 KB Output is correct
4 Correct 10 ms 460 KB Output is correct
5 Correct 12 ms 524 KB Output is correct
6 Correct 10 ms 548 KB Output is correct
7 Correct 13 ms 532 KB Output is correct
8 Correct 11 ms 588 KB Output is correct
9 Correct 13 ms 548 KB Output is correct
10 Correct 11 ms 460 KB Output is correct
11 Correct 11 ms 460 KB Output is correct
12 Correct 10 ms 460 KB Output is correct
13 Correct 9 ms 460 KB Output is correct
14 Correct 8 ms 460 KB Output is correct
15 Correct 8 ms 460 KB Output is correct
16 Correct 8 ms 460 KB Output is correct
17 Correct 8 ms 460 KB Output is correct
18 Correct 8 ms 548 KB Output is correct
19 Correct 8 ms 460 KB Output is correct
20 Correct 7 ms 460 KB Output is correct
21 Correct 9 ms 460 KB Output is correct
22 Correct 7 ms 460 KB Output is correct
23 Correct 7 ms 460 KB Output is correct
24 Correct 7 ms 460 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 460 KB Output is correct
2 Correct 10 ms 560 KB Output is correct
3 Correct 10 ms 556 KB Output is correct
4 Correct 10 ms 544 KB Output is correct
5 Correct 10 ms 560 KB Output is correct
6 Correct 10 ms 540 KB Output is correct
7 Correct 10 ms 528 KB Output is correct
8 Correct 10 ms 536 KB Output is correct
9 Correct 10 ms 552 KB Output is correct
10 Correct 10 ms 460 KB Output is correct
11 Correct 10 ms 460 KB Output is correct
12 Correct 10 ms 552 KB Output is correct
13 Correct 13 ms 512 KB Output is correct
14 Correct 1354 ms 22684 KB Output is correct
15 Correct 1367 ms 20152 KB Output is correct
16 Correct 1506 ms 25448 KB Output is correct
17 Correct 1584 ms 24352 KB Output is correct
18 Correct 1298 ms 22208 KB Output is correct
19 Correct 1235 ms 19620 KB Output is correct
20 Correct 1366 ms 23748 KB Output is correct
21 Correct 1116 ms 17912 KB Output is correct
22 Correct 1350 ms 22168 KB Output is correct
23 Correct 1326 ms 19300 KB Output is correct
24 Correct 1387 ms 23376 KB Output is correct
25 Correct 1328 ms 19396 KB Output is correct
26 Correct 1403 ms 23560 KB Output is correct