oj.uz

Submission #205860

# Submission time Handle Problem Language Result Execution time Memory
205860 2020-03-01T08:09:40 Z ics0503 Cultivation (JOI17_cultivation) C++17
5 / 100
 2000 ms 396 KB 
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int n, R, C;
struct xy { int x, y; }a[313];
struct line { int x, ys, ye, pls; };
bool sort_x(line a, line b) { if (a.x != b.x)return a.x < b.x; return a.pls < b.pls; }
int y[121212], val[121212];
bool simulate(int l, int r, int u, int d) {
	int i, j, k, yn = 0;
	vector<line>L;
	for (i = 0; i < n; i++) {
		L.push_back({ a[i].x - l, a[i].y - u, a[i].y + d, 1 });
		L.push_back({ a[i].x + r + 1, a[i].y - u,a[i].y + d,-1 });
		y[yn++] = a[i].y - u; y[yn++] = a[i].y + d;
		y[yn++] = a[i].y - u - 1; y[yn++] = a[i].y + d + 1;
	}
	L.push_back({ 1, 1, 1, 0 });
	y[yn++] = 1; y[yn++] = R;
	sort(y, y + yn);
	yn = unique(y, y + yn) - y;
	for (i = 0; i < L.size(); i++) {
		if (L[i].ys < 1)L[i].ys = 1;
		if (R < L[i].ye)L[i].ye = R;
		L[i].ys = lower_bound(y, y + yn, L[i].ys) - y;
		L[i].ye = lower_bound(y, y + yn, L[i].ye) - y;
	}
	sort(L.begin(), L.end(), sort_x);
	int s = lower_bound(y, y + yn, 1) - y;
	int e = lower_bound(y, y + yn, R) - y;
	for (i = s; i <= e; i++)val[i] = 0;
	for (i = 0; i < L.size();) {
		if (L[i].x > C)return true;
		for (j = i; j < L.size() && L[i].x == L[j].x; j++) {
			for (k = L[j].ys; k <= L[j].ye; k++) {
				val[k] += L[j].pls;
			}
		}
		if (L[i].x >= 1) {
			for (k = s; k <= e; k++) {
				if (val[k] == 0)return false;
			}
		}
		i = j;
	}
	return true;
}
int determine_d(int l, int r, int u) {
	int s = 0, e = R, ret = -1;
	while (s <= e) {
		int m = (s + e) / 2;
		if (simulate(l, r, u, m)) {
			ret = m;
			e = m - 1;
		}
		else {
			s = m + 1;
		}
	}
	return ret;
}

int main() {
	int i, j, k; scanf("%d%d%d", &C, &R, &n);
	for (i = 0; i < n; i++)scanf("%d%d", &a[i].x, &a[i].y);
	int l, r, u, d;
	int ans = 1e9;
	for (l = 0; l <= 40; l++)for (r = 0; r <= 40; r++)for (u = 0; u <= 40; u++) {
		int d = determine_d(l, r, u);

		if (d>=0&&simulate(l, r, u, d)) {
			ans = min(ans, l + r + u + d);
		}
	}
	printf("%d", ans);
	return 0;
}

Compilation message

cultivation.cpp: In function 'bool simulate(int, int, int, int)':
cultivation.cpp:23:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < L.size(); i++) {
              ~~^~~~~~~~~~
cultivation.cpp:33:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < L.size();) {
              ~~^~~~~~~~~~
cultivation.cpp:35:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (j = i; j < L.size() && L[i].x == L[j].x; j++) {
               ~~^~~~~~~~~~
cultivation.cpp: In function 'int main()':
cultivation.cpp:65:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j, k; scanf("%d%d%d", &C, &R, &n);
         ^
cultivation.cpp:65:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k; scanf("%d%d%d", &C, &R, &n);
            ^
cultivation.cpp:67:15: warning: unused variable 'd' [-Wunused-variable]
  int l, r, u, d;
               ^
cultivation.cpp:65:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int i, j, k; scanf("%d%d%d", &C, &R, &n);
               ~~~~~^~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:66:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 0; i < n; i++)scanf("%d%d", &a[i].x, &a[i].y);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 256 KB Output is correct
2 Correct 40 ms 364 KB Output is correct
3 Correct 120 ms 368 KB Output is correct
4 Correct 65 ms 376 KB Output is correct
5 Correct 364 ms 376 KB Output is correct
6 Correct 65 ms 376 KB Output is correct
7 Correct 119 ms 256 KB Output is correct
8 Correct 534 ms 376 KB Output is correct
9 Correct 118 ms 256 KB Output is correct
10 Correct 108 ms 396 KB Output is correct
11 Correct 82 ms 376 KB Output is correct
12 Correct 163 ms 380 KB Output is correct
13 Correct 113 ms 256 KB Output is correct
14 Correct 104 ms 256 KB Output is correct
15 Correct 107 ms 256 KB Output is correct
16 Correct 159 ms 256 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 256 KB Output is correct
2 Correct 40 ms 364 KB Output is correct
3 Correct 120 ms 368 KB Output is correct
4 Correct 65 ms 376 KB Output is correct
5 Correct 364 ms 376 KB Output is correct
6 Correct 65 ms 376 KB Output is correct
7 Correct 119 ms 256 KB Output is correct
8 Correct 534 ms 376 KB Output is correct
9 Correct 118 ms 256 KB Output is correct
10 Correct 108 ms 396 KB Output is correct
11 Correct 82 ms 376 KB Output is correct
12 Correct 163 ms 380 KB Output is correct
13 Correct 113 ms 256 KB Output is correct
14 Correct 104 ms 256 KB Output is correct
15 Correct 107 ms 256 KB Output is correct
16 Correct 159 ms 256 KB Output is correct
17 Correct 1768 ms 376 KB Output is correct
18 Execution timed out 2080 ms 256 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 256 KB Output is correct
2 Correct 40 ms 364 KB Output is correct
3 Correct 120 ms 368 KB Output is correct
4 Correct 65 ms 376 KB Output is correct
5 Correct 364 ms 376 KB Output is correct
6 Correct 65 ms 376 KB Output is correct
7 Correct 119 ms 256 KB Output is correct
8 Correct 534 ms 376 KB Output is correct
9 Correct 118 ms 256 KB Output is correct
10 Correct 108 ms 396 KB Output is correct
11 Correct 82 ms 376 KB Output is correct
12 Correct 163 ms 380 KB Output is correct
13 Correct 113 ms 256 KB Output is correct
14 Correct 104 ms 256 KB Output is correct
15 Correct 107 ms 256 KB Output is correct
16 Correct 159 ms 256 KB Output is correct
17 Correct 1768 ms 376 KB Output is correct
18 Execution timed out 2080 ms 256 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2090 ms 256 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 256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 256 KB Output is correct
2 Correct 40 ms 364 KB Output is correct
3 Correct 120 ms 368 KB Output is correct
4 Correct 65 ms 376 KB Output is correct
5 Correct 364 ms 376 KB Output is correct
6 Correct 65 ms 376 KB Output is correct
7 Correct 119 ms 256 KB Output is correct
8 Correct 534 ms 376 KB Output is correct
9 Correct 118 ms 256 KB Output is correct
10 Correct 108 ms 396 KB Output is correct
11 Correct 82 ms 376 KB Output is correct
12 Correct 163 ms 380 KB Output is correct
13 Correct 113 ms 256 KB Output is correct
14 Correct 104 ms 256 KB Output is correct
15 Correct 107 ms 256 KB Output is correct
16 Correct 159 ms 256 KB Output is correct
17 Correct 1768 ms 376 KB Output is correct
18 Execution timed out 2080 ms 256 KB Time limit exceeded
19 Halted 0 ms 0 KB -