답안 #413881

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
413881	2021-05-29T16:33:26 Z	600Mihnea	Cultivation (JOI17_cultivation)	C++17	5 / 100	2000 ms	262148 KB

cultivation

#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 <= cnt; i++) {
    int x, y;
    cin >> x >> y;
    s.insert({x, y});
  }

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

  return 0;
}

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	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	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	2 ms	204 KB	Output is correct
7	Correct	6 ms	336 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	2 ms	204 KB	Output is correct
10	Correct	1 ms	320 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	316 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	2 ms	204 KB	Output is correct
15	Correct	48 ms	332 KB	Output is correct
16	Correct	2 ms	332 KB	Output is correct

Subtask #2

0 / 10.0

#	결과	실행 시간	메모리	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	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	2 ms	204 KB	Output is correct
7	Correct	6 ms	336 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	2 ms	204 KB	Output is correct
10	Correct	1 ms	320 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	316 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	2 ms	204 KB	Output is correct
15	Correct	48 ms	332 KB	Output is correct
16	Correct	2 ms	332 KB	Output is correct
17	Execution timed out	2098 ms	1332 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #3

0 / 15.0

#	결과	실행 시간	메모리	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	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	2 ms	204 KB	Output is correct
7	Correct	6 ms	336 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	2 ms	204 KB	Output is correct
10	Correct	1 ms	320 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	316 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	2 ms	204 KB	Output is correct
15	Correct	48 ms	332 KB	Output is correct
16	Correct	2 ms	332 KB	Output is correct
17	Execution timed out	2098 ms	1332 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #4

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	1175 ms	262148 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	1175 ms	262148 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 20.0

#	결과	실행 시간	메모리	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	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	2 ms	204 KB	Output is correct
7	Correct	6 ms	336 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	2 ms	204 KB	Output is correct
10	Correct	1 ms	320 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	316 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	2 ms	204 KB	Output is correct
15	Correct	48 ms	332 KB	Output is correct
16	Correct	2 ms	332 KB	Output is correct
17	Execution timed out	2098 ms	1332 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-