oj.uz

Submission #45571

# Submission time Handle Problem Language Result Execution time Memory
45571 2018-04-15T13:30:40 Z maksim_gaponov Cultivation (JOI17_cultivation) C++14
5 / 100
 5 ms 1000 KB 
#define _CRT_SECURE_NO_WARNINGS
#ifdef _DEBUG
#define FILE_IN "input.txt"
#define FILE_OUT "output.txt"
#endif
#include <iostream>
#include <cstdlib>
#include <climits>
#include <set>
#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <vector>
#include <algorithm>
#include <bitset>

using namespace std;
typedef long long ll;

void openFiles() {
#ifdef _DEBUG
	assert(freopen(FILE_IN, "r", stdin));
	assert(freopen(FILE_OUT, "w", stdout));
#endif
}

void IOoptimize() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

const int MAXR = 4;
const int MAXC = 4;
int ans = INT_MAX;
int r, c;

bool get(const bitset<MAXR * MAXC>& bs, int i, int j) {
	if (i < 0 || j < 0 || i >= r || j >= c)
		return false;
	//cout << "get " << i * c + j << " " << i << " " << j << "\n";
	return bs[i * c + j];
}

void check(bitset<MAXR * MAXC> state, int time) {
	if (time >= ans)
		return;
	if (state.count() == r * c) {
		ans = min(ans, time);
		return;
	}
	//cout << state << " = state\n";
	for (int x_dir = -1; x_dir <= 1; x_dir++) {
		for (int y_dir = -1; y_dir <= 1; y_dir++) {
			if ((x_dir && y_dir) || !(x_dir || y_dir))
				continue;
			//cout << x_dir << " " << y_dir << "\n";
			bitset<MAXR * MAXC> new_state;
			for (int i = 0; i < r; i++) {
				for (int j = 0; j < c; j++) {
					//cout << get(state, i, j);
					if (get(state, i, j) || get(state, i - x_dir, j - y_dir)) {
						new_state.set(i * c + j);
					}
				}
				//cout << "\n";
			}
			/*for (int i = 0; i < r; i++) {
				for (int j = 0; j < c; j++) {
					cout << get(new_state, i, j);
				}
				cout << "\n";
			}*/
			//cout << new_state << "\n";
			if (state.count() == new_state.count())
				continue;
			check(new_state, time + 1);
		}
	}
}

int main() {
	openFiles();
	IOoptimize();
	cin >> r >> c;
	int n;
	cin >> n;
	vector<int> x(n), y(n);
	bitset<MAXR * MAXC> start;
	for (int i = 0; i < n; ++i) {
		cin >> x[i] >> y[i];
		x[i]--;
		y[i]--;
		start.set(x[i] * c + y[i]);
	}
	//cout << start;
	//return 0;
	check(start, 0);
	cout << ans;
	return 0;
}

Compilation message

cultivation.cpp: In function 'void check(std::bitset<16>, int)':
cultivation.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (state.count() == r * c) {
      ~~~~~~~~~~~~~~^~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 496 KB Output is correct
3 Correct 2 ms 496 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Correct 2 ms 496 KB Output is correct
6 Correct 2 ms 496 KB Output is correct
7 Correct 2 ms 496 KB Output is correct
8 Correct 2 ms 584 KB Output is correct
9 Correct 2 ms 708 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 720 KB Output is correct
12 Correct 2 ms 756 KB Output is correct
13 Correct 2 ms 756 KB Output is correct
14 Correct 2 ms 756 KB Output is correct
15 Correct 2 ms 756 KB Output is correct
16 Correct 2 ms 756 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 496 KB Output is correct
3 Correct 2 ms 496 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Correct 2 ms 496 KB Output is correct
6 Correct 2 ms 496 KB Output is correct
7 Correct 2 ms 496 KB Output is correct
8 Correct 2 ms 584 KB Output is correct
9 Correct 2 ms 708 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 720 KB Output is correct
12 Correct 2 ms 756 KB Output is correct
13 Correct 2 ms 756 KB Output is correct
14 Correct 2 ms 756 KB Output is correct
15 Correct 2 ms 756 KB Output is correct
16 Correct 2 ms 756 KB Output is correct
17 Runtime error 5 ms 980 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 496 KB Output is correct
3 Correct 2 ms 496 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Correct 2 ms 496 KB Output is correct
6 Correct 2 ms 496 KB Output is correct
7 Correct 2 ms 496 KB Output is correct
8 Correct 2 ms 584 KB Output is correct
9 Correct 2 ms 708 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 720 KB Output is correct
12 Correct 2 ms 756 KB Output is correct
13 Correct 2 ms 756 KB Output is correct
14 Correct 2 ms 756 KB Output is correct
15 Correct 2 ms 756 KB Output is correct
16 Correct 2 ms 756 KB Output is correct
17 Runtime error 5 ms 980 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 1000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 1000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 496 KB Output is correct
3 Correct 2 ms 496 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Correct 2 ms 496 KB Output is correct
6 Correct 2 ms 496 KB Output is correct
7 Correct 2 ms 496 KB Output is correct
8 Correct 2 ms 584 KB Output is correct
9 Correct 2 ms 708 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 720 KB Output is correct
12 Correct 2 ms 756 KB Output is correct
13 Correct 2 ms 756 KB Output is correct
14 Correct 2 ms 756 KB Output is correct
15 Correct 2 ms 756 KB Output is correct
16 Correct 2 ms 756 KB Output is correct
17 Runtime error 5 ms 980 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -