oj.uz

Submission #413879

# Submission time Handle Problem Language Result Execution time Memory
413879 2021-05-29T16:31:34 Z 600Mihnea Cultivation (JOI17_cultivation) C++17
0 / 100
 2000 ms 332 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m, cnt;

bool valid(pair<int, int> a) {
  return 1 <= a.first && a.first <= n && 1 <= a.second && a.second <= m;
}



set<pair<int, int>> get(set<pair<int, int>> a, int dx, int dy) {
  set<pair<int, int>> sol = a;
  for (auto &it : a) {
    sol.insert({it.first + dx, it.second + dy});
  }
  for (auto &it : sol) {
    if (valid(it)) {
      a.insert(it);
    }
  }
  return a;
}

int bkt(set<pair<int, int>> s) {
  if ((int) s.size() == n * m) return 0;

  int cnt = 0;
  vector<set<pair<int, int>>> all;
  for (int dx = -1; dx <= +1; dx++) {
    for (int dy = -1; dy <= +1; dy++) {
      if (abs(dx) + abs(dy) != 1) continue;
      cnt++;
      set<pair<int, int>> s2 = get(s, dx, dy);
      ///cout << " : " << (int) s.size() << " and " << (int) s2.size() << "\n";
      if ((int) s2.size() > (int) s.size()) {
        all.push_back(s2);
      }
    }
  }
  assert(cnt == 4);


  assert(!all.empty());

  int best = (int) 1e9;

  for (auto &s2 : all) {
    best = min(best, bkt(s2) + 1);
  }

  return best;
}


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

  ///freopen ("input", "r", stdin);

  cin >> n >> m >> cnt;
  set<pair<int, int>> s;

  for (int i = 1; i <= n; i++) {
    int x, y;
    cin >> x >> y;
    s.insert({x, y});
  }

  cout << bkt(s) << "\n";

  return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Incorrect 13 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Incorrect 13 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Incorrect 13 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2090 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2090 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Incorrect 13 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -