Submission #1181067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181067		jbareja	The Kingdom of JOIOI (JOI17_joioi)	C++20	0 / 100	0 ms	320 KiB

joioi

#include <bits/stdc++.h>

using namespace std;

int H; // liczba wierszy
int W; // liczba kolumn

vector<vector<int>> altitude;
vector<vector<int>> occupation;
vector<vector<int>> cnt_x;
vector<vector<int>> cnt_o;

int maxi = 0, mini = 1e9+7;

void occupation_for_delta(int d) {
	for (int i=1; i<=H; i++) {
		for (int j=1; j<=W; j++) {
			const auto& now = altitude[i][j];
			bool first = abs(mini - now) <= d;
			bool second = abs(maxi - now) <= d;
			if (first && second) occupation[i][j] = 0;
			else if (first) occupation[i][j] = 1;
			else if (second) occupation[i][j] = 2;
			else occupation[i][j] = 3;
		}
	}
}

void count_prefix_sums() {
	for (int i=0; i<=H+1; i++) {
		cnt_x[i][0] = 0;
		cnt_o[i][0] = 0;
	}
	for (int j=0; j<=W+1; j++) {
		cnt_x[0][j] = 0;
		cnt_o[0][j] = 0;
	}
	for (int i=1; i<=H+1; i++) {
		for (int j=1; j<=W+1; j++) {
			cnt_x[i][j] = cnt_x[i-1][j] + cnt_x[i][j-1] - cnt_x[i-1][j-1];
			cnt_o[i][j] = cnt_o[i-1][j] + cnt_o[i][j-1] - cnt_o[i-1][j-1];
			if (i <= H && j <= W) {
				cnt_x[i][j] += (occupation[i][j] == 1);
				cnt_o[i][j] += (occupation[i][j] == 2);
			}
		}
	}
}

int sum(vector<vector<int>>& cnt, int i1, int j1, int i2, int j2) {
	if (i1 > i2) swap(i1, i2);
	if (j1 > j2) swap(j1, j2);
	return cnt[i2][j2] - cnt[i1-1][j2] - cnt[i2][j1-1] + cnt[i1-1][j1-1];
}

bool check_quarter(int ip, int jp) {
	for (int i=1; i<=H; i++) for (int j=1; j<=H; j++) if (occupation[i][j] == 2 && sum(cnt_x, i, j, ip, jp)) return false;
	return true;
}

bool check_occupation() {
	// przejście po wierszach
	for (int i=1; i<=H; i++) {
		// sprawdzam wiersz
		bool x = false; // occ = 1
		bool o = false; // occ = 2
		int first_found = 0;
		for (int j=1; j<=W; j++) {
			if (occupation[i][j] == 1) {
				x = true;
				if (first_found == 0) first_found = 1;
				if (first_found == 1 && o) return false;
			}
			else if (occupation[i][j] == 2) {
				o = true;
				if (first_found == 0) first_found = 2;
				if (first_found == 2 && x) return false;
			}
			else if (occupation[i][j] == 3) {
				return false;
			}
		}
	}
	// przejście po kolumnach
	for (int j=1; j<=W; j++) {
		// sprawdzam kolumnę
		bool x = false; // occ = 1
		bool o = false; // occ = 2
		int first_found = 0;
		for (int i=1; i<=H; i++) {
			if (occupation[i][j] == 1) {
				x = true;
				if (first_found == 0) first_found = 1;
				if (first_found == 1 && o) return false;
			}
			else if (occupation[i][j] == 2) {
				o = true;
				if (first_found == 0) first_found = 2;
				if (first_found == 2 && x) return false;
			}
			else if (occupation[i][j] == 3) {
				return false;
			}
		}
	}
	// przejście po rogach
	vector<int> cnt(4);
	cnt[occupation[1][1]]++;
	cnt[occupation[1][W]]++;
	cnt[occupation[H][1]]++;
	cnt[occupation[H][W]]++;
	if (cnt[1] == 4 || cnt[2] == 4) return false;
	// przejście po rogach 2
	count_prefix_sums();
	if (check_quarter(1,1)) return true;
	if (check_quarter(1,W)) return true;
	if (check_quarter(H,1)) return true;
	if (check_quarter(H,W)) return true;
	return false;
}

void print_occupation() {
	vector<char> temp = { '.', 'x', 'o', '@' };
	for (int i=1; i<=H; i++) {
		for (int j=1; j<=W; j++) cout << temp[occupation[i][j]];
		cout << '\n';
	}
}

void print_prefix_sums() {
	for (int i=1; i<=H; i++) {
		for (int j=1; j<=W; j++) cout << cnt_x[i][j] << ' ';
		cout << '\n';
	}
	cout << '\n';
	for (int i=1; i<=H; i++) {
		for (int j=1; j<=W; j++) cout << cnt_o[i][j] << ' ';
		cout << '\n';
	}
	cout << '\n';
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> H >> W;
	altitude.assign(H+1, vector<int>(W+1, 0));
	occupation.assign(H+1, vector<int>(W+1, 0));
	cnt_o.assign(H+2, vector<int>(W+2, 0));
	cnt_x.assign(H+2, vector<int>(W+2, 0));

	for (int i=1; i<=H; i++) for (int j=1; j<=W; j++) {
		cin >> altitude[i][j];
		maxi = max(maxi,altitude[i][j]);
		mini = min(mini, altitude[i][j]);
	}

	int low = 0;
	int high = maxi + 7;
	while (low != high) {
		int mid = (low + high) / 2;
		occupation_for_delta(mid);
		if (check_occupation()) high = mid;
		else low = mid + 1;
	}

	cout << low << '\n';
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40