Submission #45571

#	Time	Username	Problem	Language	Result	Execution time	Memory
45571		maksim_gaponov	Cultivation (JOI17_cultivation)	C++14	5 / 100	5 ms	1000 KiB

cultivation

#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 (stderr)

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 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 20