Submission #840436

#	Time	Username	Problem	Language	Result	Execution time	Memory
840436		catalystgma	Soccer Stadium (IOI23_soccer)	C++17	22 / 100	4550 ms	134884 KiB

soccer

#include <bits/stdc++.h>
#define maxn 2000

bool inside(int n, int i, int j) {
	return i  >= 0 && i < n && j >= 0 && j < n;
}

std::vector<std::pair<int, int>> neighs(int n, int i, int j, std::vector<std::vector<int>> &v) {
	std::vector<std::pair<int, int>> sol;
	for (int dy: {-1, 0, 1}) {
		for (int dx: {-1, 0, 1}) {
			if (abs(dy) != abs(dx) && inside(n, i+dy, j+dx) && v[i+dy][j+dx] == 0) {
				sol.emplace_back(i + dy, j + dx);
			}
		}
	}

	return sol;
}

struct Pos {
	int y, x;
	bool isDirOrizontal, haveRemChange;

	Pos(int y_, int x_, bool isdo, bool hrc) {
		y = y_;
		x = x_;
		isDirOrizontal = isdo;
		haveRemChange = hrc;
	}
};

int viz[maxn+5][maxn+5][2]; ///punct, directie = max schimbari ramase.

bool isFullMapOk(int n, std::vector<std::vector<int>> &v) {
	std::vector<std::pair<int, std::pair<int, int>>> parti;
	int i, j, z;
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			viz[i][j][0] = viz[i][j][1] = -1;
			if (v[i][j] == 0) {
				parti.emplace_back(neighs(n, i, j, v).size(), std::make_pair(i, j));
			}
		}
	}

	std::sort(parti.begin(), parti.end());

	clock_t te = clock() + 4 * CLOCKS_PER_SEC;
	for (auto p: parti) {
		for (i = 0; i < n; i++) {
			for (j = 0; j < n; j++) {
				viz[i][j][0] = viz[i][j][1] = -1;
			}
		}

		std::queue<Pos> qu;

		viz[p.second.first][p.second.second][0] = 1;
		qu.emplace(p.second.first, p.second.second, false, true);

		viz[p.second.first][p.second.second][1] = 1;
		qu.emplace(p.second.first, p.second.second, true, true);

		while (!qu.empty()) { ///daca nu merge campul, ma astept sa crape din cauza unui patrat cu nr mic de vecini.
			auto now = qu.front();
			qu.pop();

			for (int _ = 0; _ < 2; _++) {
				if (_) { ///incerc sa schimb directia.
					if (!now.haveRemChange) break;
					now.haveRemChange = false;
					now.isDirOrizontal ^= 1;
				}

				for (int sh: {-1, 1}) {
					if (now.isDirOrizontal) now.x += sh;
					else now.y += sh;

					if (inside(n, now.y, now.x) && v[now.y][now.x] == 0 && viz[now.y][now.x][now.isDirOrizontal] < now.haveRemChange) {
						viz[now.y][now.x][now.isDirOrizontal] = now.haveRemChange;
						qu.emplace(now.y, now.x, now.isDirOrizontal, now.haveRemChange);
					}

					if (now.isDirOrizontal) now.x -= sh;
					else now.y -= sh;
				}
			}
		}

		for (i = 0; i < n; i++) {
			for (j = 0; j < n; j++) {
				if (v[i][j] == 0 && std::max(viz[i][j][0], viz[i][j][1]) < 0) {
					return false;
				}
			}
		}

		if (clock() > te) {
			break;
		}
	}

	return true;
}

int continua(int n, std::vector<std::vector<int>> &v) {
	int y = -1, x = -1, cnt0s = 0;
	int i, j, z;
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			if (v[i][j] == 0) {
				y = i;
				x = j;
				cnt0s++;
			}
		}
	}

	std::queue<std::pair<int, int>> qu;
	std::vector<std::pair<int, int>> got;

	qu.emplace(y, x);
	got.emplace_back(y, x);
	v[y][x] = -1;

	while (!qu.empty()) {
		std::tie(y, x) = qu.front();
		qu.pop();

		for (auto p: neighs(n, y, x, v)) {
			if (v[p.first][p.second] != -1) {
				qu.push(p);
				got.push_back(p);
				v[p.first][p.second] = -1;
			}
		}
	}

	for (auto &p: got) {
		v[p.first][p.second] = 0;
	}

	return ((int)got.size() == cnt0s? cnt0s: -1);
}

int biggest_stadium(int n, std::vector<std::vector<int>> v) {
	int cnt1s = 0, y = -1, x = -1;

	int i, j, z;
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			if (v[i][j] == 1) {
				cnt1s++;
				y = i;
				x = j;
			}
		}
	}

	if (cnt1s <= 1) {
		if (cnt1s == 0) {
			return n * n;
		}

		return n * n - std::min(n - x, x + 1) * std::min(n - y, y + 1);
	}

	///incerc sa vad daca toata harta e ok.

	///zona continua?
	int cnt0s = continua(n, v);
	if (cnt0s == -1) {
		return -1;
	}

	if (isFullMapOk(n, v)) {
		return cnt0s;
	}

	return -1;
}

Compilation message (stderr)

soccer.cpp: In function 'bool isFullMapOk(int, std::vector<std::vector<int> >&)':
soccer.cpp:37:12: warning: unused variable 'z' [-Wunused-variable]
   37 |  int i, j, z;
      |            ^
soccer.cpp: In function 'int continua(int, std::vector<std::vector<int> >&)':
soccer.cpp:109:12: warning: unused variable 'z' [-Wunused-variable]
  109 |  int i, j, z;
      |            ^
soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:150:12: warning: unused variable 'z' [-Wunused-variable]
  150 |  int i, j, z;
      |            ^

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 2 / 8
• Subtask 3: 5.5 / 22
• Subtask 4: 4.5 / 18
• Subtask 5: 4 / 16
• Subtask 6: 0 / 30