oj.uz

Submission #421154

# Submission time Handle Problem Language Result Execution time Memory
421154 2021-06-08T19:21:58 Z rama_pang Izvanzemaljci (COI21_izvanzemaljci) C++17
68 / 100
 1565 ms 20736 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;
              }
            }
          }
        }
      }
      cout << rot << '\n';
      cout << boundLftX << ' ' << boundRgtX << ' ' << boundLftY << ' ' << boundRgtY << '\n';
      for (auto i : alive) cout << X[i] << ' ' << Y[i] << endl;
      assert(false);
      return 1e18;
    };

    const auto SolveK2 = [&](vector<int> alive, int vert, lint boundLftX, int trace) -> lint {
      if (alive.empty()) return 0;

      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 >= 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]);
      };

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

        if (res == 1e18) {
          return 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 == 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 res;
          }
        }
      } else {
        for (int i = 0; i < int(alive.size()); i++) {
          if (!(i + 1 == alive.size() || X[alive[i + 1]] != X[alive[i]])) {
            continue;
          }
          lint len = CalcPref(i);
          lint upTo = (i + 1 == 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 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 == alive.size() || X[alive[i + 1]] != X[alive[i]])) {
            continue;
          }
          lint len = CalcPref(i);
          lint upTo = (i + 1 == 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 res;
          }
        }
      }

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

      return 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);

      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<lint> coordX = X;
      sort(begin(coordX), end(coordX));
      coordX.resize(unique(begin(coordX), end(coordX)) - begin(coordX));

      int lo = 0, hi = coordX.size();
      while (lo < hi) {
        int md = (lo + hi + 1) / 2;
        vector<int> other;
        int idx = -1;
        for (int i = 0; i < int(alive.size()); i++) {
          if (X[alive[i]] > coordX[md]) {
            other.emplace_back(alive[i]);
          } else {
            idx = i;
          }
        }
        lint getOther = min(SolveK2(other, 0, coordX[md] + 1, 0),
                            SolveK2(other, 1, coordX[md] + 1, 0));
        if (CalcPref(idx) <= getOther) {
          lo = md;
        } else {
          hi = md - 1;
        }
      }

      vector<int> suff = alive;
      reverse(begin(suff), end(suff));
      for (int i = 0; i < int(alive.size()); i++) {
        suff.pop_back();
        if (!(i + 1 == alive.size() || X[alive[i + 1]] != X[alive[i]])) {
          continue;
        }
        if (abs(i - lo) > 2) 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 == alive.size() || X[alive[i + 1]] != X[alive[i]])) {
          continue;
        }
        if (abs(i - lo) > 2) 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) {
      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);
      }
    };

    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 (ans.size() < K) {
    ans.push_back({lint(-3e9 + 2 * it), lint(3e9), 1});
    it++;
  }

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

Compilation message

izvanzemaljci.cpp: In lambda function:
izvanzemaljci.cpp:145:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |         if (i < 0 || i >= alive.size()) return 0;
      |                      ~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp: In lambda function:
izvanzemaljci.cpp:150:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |         if (i < 0 || i >= alive.size()) return 0;
      |                      ~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp: In lambda function:
izvanzemaljci.cpp:156:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |           if (!(i + 1 == alive.size() || Y[alive[i + 1]] != Y[alive[i]])) {
      |                 ~~~~~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp:172:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |           if (!(i + 1 == alive.size() || Y[alive[i + 1]] != Y[alive[i]])) {
      |                 ~~~~~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp:183:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |           if (!(i + 1 == alive.size() || X[alive[i + 1]] != X[alive[i]])) {
      |                 ~~~~~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp:187:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  187 |           lint upTo = (i + 1 == alive.size()) ? 1e18 : (X[alive[i + 1]] - 1);
      |                        ~~~~~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp:202:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  202 |           if (!(i + 1 == alive.size() || X[alive[i + 1]] != X[alive[i]])) {
      |                 ~~~~~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp:206:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  206 |           lint upTo = (i + 1 == alive.size()) ? 1e18 : (X[alive[i + 1]] - 1);
      |                        ~~~~~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp: In lambda function:
izvanzemaljci.cpp:261:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  261 |         if (i < 0 || i >= alive.size()) return 0;
      |                      ~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp: In lambda function:
izvanzemaljci.cpp:266:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  266 |         if (i < 0 || i >= alive.size()) return 0;
      |                      ~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp: In lambda function:
izvanzemaljci.cpp:299:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  299 |         if (!(i + 1 == alive.size() || X[alive[i + 1]] != X[alive[i]])) {
      |               ~~~~~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp:317:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  317 |         if (!(i + 1 == alive.size() || X[alive[i + 1]] != X[alive[i]])) {
      |               ~~~~~~^~~~~~~~~~~~~~~
izvanzemaljci.cpp:265:18: warning: variable 'CalcSuff' set but not used [-Wunused-but-set-variable]
  265 |       const auto CalcSuff = [&](int i) -> lint {
      |                  ^~~~~~~~
izvanzemaljci.cpp: In function 'int main()':
izvanzemaljci.cpp:397: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]
  397 |   while (ans.size() < K) {
      |          ~~~~~~~~~~~^~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from izvanzemaljci.cpp:1:
izvanzemaljci.cpp: In lambda function:
izvanzemaljci.cpp:403:22: 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]
  403 |     assert(sq.size() <= K);
      |            ~~~~~~~~~~^~~~
izvanzemaljci.cpp: In lambda function:
izvanzemaljci.cpp:368:5: warning: control reaches end of non-void function [-Wreturn-type]
  368 |     };
      |     ^

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 1 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 156 ms 4212 KB Output is correct
8 Correct 153 ms 4196 KB Output is correct
9 Correct 153 ms 4204 KB Output is correct
10 Correct 165 ms 4216 KB Output is correct
11 Correct 155 ms 4200 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 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 0 ms 272 KB Output is correct
6 Correct 0 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 230 ms 12192 KB Output is correct
11 Correct 218 ms 12032 KB Output is correct
12 Correct 223 ms 12112 KB Output is correct
13 Correct 241 ms 12744 KB Output is correct
14 Correct 221 ms 12624 KB Output is correct
15 Correct 230 ms 12172 KB Output is correct
16 Correct 226 ms 12592 KB Output is correct
17 Correct 205 ms 11268 KB Output is correct
18 Correct 197 ms 10900 KB Output is correct
19 Correct 179 ms 9948 KB Output is correct
20 Correct 189 ms 10652 KB Output is correct
21 Correct 228 ms 12196 KB Output is correct
22 Correct 227 ms 11964 KB Output is correct
23 Correct 229 ms 12248 KB Output is correct

Subtask #3
12.0 / 12.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 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 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 280 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 0 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 204 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 0 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 7 ms 460 KB Output is correct
2 Correct 8 ms 520 KB Output is correct
3 Correct 9 ms 528 KB Output is correct
4 Correct 7 ms 460 KB Output is correct
5 Correct 9 ms 504 KB Output is correct
6 Correct 9 ms 460 KB Output is correct
7 Correct 8 ms 516 KB Output is correct
8 Correct 7 ms 588 KB Output is correct
9 Correct 7 ms 460 KB Output is correct
10 Correct 7 ms 588 KB Output is correct
11 Correct 7 ms 460 KB Output is correct
12 Correct 7 ms 460 KB Output is correct
13 Correct 6 ms 460 KB Output is correct
14 Correct 6 ms 460 KB Output is correct
15 Correct 6 ms 460 KB Output is correct
16 Correct 8 ms 460 KB Output is correct
17 Correct 5 ms 460 KB Output is correct
18 Correct 5 ms 460 KB Output is correct
19 Correct 6 ms 504 KB Output is correct
20 Correct 8 ms 460 KB Output is correct
21 Correct 6 ms 620 KB Output is correct
22 Correct 7 ms 460 KB Output is correct
23 Correct 5 ms 460 KB Output is correct
24 Correct 5 ms 460 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 520 KB Output is correct
2 Correct 8 ms 588 KB Output is correct
3 Correct 7 ms 460 KB Output is correct
4 Correct 9 ms 460 KB Output is correct
5 Correct 7 ms 540 KB Output is correct
6 Correct 7 ms 460 KB Output is correct
7 Correct 7 ms 460 KB Output is correct
8 Correct 8 ms 520 KB Output is correct
9 Correct 7 ms 520 KB Output is correct
10 Correct 7 ms 460 KB Output is correct
11 Correct 8 ms 460 KB Output is correct
12 Correct 7 ms 460 KB Output is correct
13 Correct 7 ms 532 KB Output is correct
14 Correct 1231 ms 15892 KB Output is correct
15 Correct 1433 ms 19452 KB Output is correct
16 Correct 1246 ms 20736 KB Output is correct
17 Correct 1565 ms 19936 KB Output is correct
18 Incorrect 1392 ms 19080 KB Output isn't correct
19 Halted 0 ms 0 KB -