oj.uz

Submission #420937

# Submission time Handle Problem Language Result Execution time Memory
420937 2021-06-08T15:06:05 Z rama_pang Izvanzemaljci (COI21_izvanzemaljci) C++17
56 / 100
 3000 ms 15408 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];
  }

  // 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 conf, 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) {
        if (vert == 1 && conf == 0) {
          assert(SolveK1(L, pref, 2, trace));
          assert(SolveK1(L, suff, 3, trace));          
        }
        if (vert == 1 && conf == 1) {
          assert(SolveK1(L, pref, 1, trace));
          assert(SolveK1(L, suff, 0, trace));          
        }
        if (vert == 0 && conf == 0) {
          assert(SolveK1(L, pref, 2, trace));
          assert(SolveK1(L, suff, 1, trace));          
        }
        if (vert == 0 && conf == 1) {
          assert(SolveK1(L, pref, 3, trace));
          assert(SolveK1(L, suff, 0, trace));
        }
        // 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;
      vector<int> other;
      for (int i = last + 1; i < int(alive.size()); i++) {
        other.emplace_back(alive[i]);
      }
      if (SolveK2(L, other, 1 - vert, 1, trace)) {
        if (trace) {
          other.clear();
          for (int i = 0; i <= last; i++) {
            other.emplace_back(alive[i]);
          }
          SolveK1(L, other, 2, trace);
        }
        return true;
      }

      }
    }
    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, 1, 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;
      vector<int> other;
      for (int i = 0; i < last; i++) {
        other.emplace_back(alive[i]);
      }
      if (SolveK2(L, other, 1 - vert, 0, 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;
      }
      }
    }
    if (last != -1) {
      vector<int> other;
      for (int i = 0; i < last; i++) {
        other.emplace_back(alive[i]);
      }
      if (SolveK2(L, other, 1 - vert, 0, 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, 0, trace)) {
        return true;
      }
      ans.clear();
      if (SolveK2(L, alive, 1, 0, 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 ValidAnswer = [&](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;
            }
          }
        }
      }
    }
    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;
}

Compilation message

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:205:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  205 |       if (i < 0 || i >= alive.size()) return 0;
      |                    ~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp: In lambda function:
izvanzemaljci.cpp:209:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  209 |       if (i < 0 || i >= alive.size()) return 0;
      |                    ~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp: In lambda function:
izvanzemaljci.cpp:216:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  216 |       if (!(i + 1 == alive.size() ||
      |             ~~~~~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp:320:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  320 |         if (!(j + 1 == alive.size() ||
      |               ~~~~~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp: In function 'int main()':
izvanzemaljci.cpp:422: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]
  422 |   while (ans.size() < K) {
      |          ~~~~~~~~~~~^~~

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 0 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 68 ms 3816 KB Output is correct
8 Correct 77 ms 3812 KB Output is correct
9 Correct 67 ms 3808 KB Output is correct
10 Correct 68 ms 3796 KB Output is correct
11 Correct 67 ms 3804 KB Output is correct

Subtask #2
21.0 / 21.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 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 445 ms 12360 KB Output is correct
11 Correct 463 ms 12264 KB Output is correct
12 Correct 459 ms 12232 KB Output is correct
13 Correct 465 ms 12300 KB Output is correct
14 Correct 459 ms 12332 KB Output is correct
15 Correct 439 ms 12308 KB Output is correct
16 Correct 508 ms 12220 KB Output is correct
17 Correct 351 ms 11260 KB Output is correct
18 Correct 343 ms 10896 KB Output is correct
19 Correct 367 ms 10036 KB Output is correct
20 Correct 405 ms 10776 KB Output is correct
21 Correct 368 ms 12328 KB Output is correct
22 Correct 426 ms 12296 KB Output is correct
23 Correct 474 ms 12200 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 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 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Incorrect 1 ms 204 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 460 KB Output is correct
2 Correct 172 ms 492 KB Output is correct
3 Correct 220 ms 484 KB Output is correct
4 Correct 160 ms 460 KB Output is correct
5 Correct 158 ms 492 KB Output is correct
6 Correct 204 ms 476 KB Output is correct
7 Correct 189 ms 492 KB Output is correct
8 Correct 135 ms 460 KB Output is correct
9 Correct 143 ms 476 KB Output is correct
10 Correct 186 ms 484 KB Output is correct
11 Correct 164 ms 460 KB Output is correct
12 Correct 228 ms 480 KB Output is correct
13 Correct 247 ms 460 KB Output is correct
14 Correct 425 ms 460 KB Output is correct
15 Correct 188 ms 460 KB Output is correct
16 Correct 291 ms 468 KB Output is correct
17 Correct 469 ms 460 KB Output is correct
18 Correct 531 ms 464 KB Output is correct
19 Correct 392 ms 464 KB Output is correct
20 Correct 389 ms 460 KB Output is correct
21 Correct 589 ms 580 KB Output is correct
22 Correct 573 ms 460 KB Output is correct
23 Correct 467 ms 460 KB Output is correct
24 Correct 541 ms 460 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 480 KB Output is correct
2 Correct 230 ms 496 KB Output is correct
3 Correct 140 ms 460 KB Output is correct
4 Correct 206 ms 492 KB Output is correct
5 Correct 259 ms 460 KB Output is correct
6 Correct 224 ms 460 KB Output is correct
7 Correct 125 ms 460 KB Output is correct
8 Correct 134 ms 460 KB Output is correct
9 Correct 158 ms 460 KB Output is correct
10 Correct 239 ms 476 KB Output is correct
11 Correct 192 ms 460 KB Output is correct
12 Correct 274 ms 460 KB Output is correct
13 Correct 229 ms 492 KB Output is correct
14 Execution timed out 3066 ms 15408 KB Time limit exceeded
15 Halted 0 ms 0 KB -