Submission #1049092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049092		MinaRagy06	Building Skyscrapers (CEOI19_skyscrapers)	C++17	0 / 100	2927 ms	1048576 KiB

skyscrapers

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define ll long long
#define SZ(x) (int) x.size()

int dx[8] = {0, -1, 0, 1, -1, -1, 1, 1};
int dy[8] = {1, 0, -1, 0, 1, -1, 1, -1};
const int N = 2005;
bool vis[N], vis2[N * 9];
bool check(vector<array<int, 3>> a) {
	if (a.empty()) {
		return 1;
	}
	for (int i = 0; i < SZ(a); i++) {
		vis[i] = 0;
	}
	queue<int> q;
	q.push(0);
	int cnt = 0;
	vis[0] = 1;
	cnt++;
	auto getp = [&] (int x, int y) {
		return lower_bound(a.begin(), a.end(), (array<int, 3>) {x, y, -1}) - a.begin();
	};
	while (SZ(q)) {
		int i = q.front();
		int x = a[i][0], y = a[i][1];
		q.pop();
		for (int k = 0; k < 8; k++) {
			int newx = x + dx[k], newy = y + dy[k];
			int p = getp(newx, newy);
			if (p < SZ(a) && a[p][0] == newx && a[p][1] == newy && !vis[p]) {
				q.push(p);
				vis[p] = 1;
				cnt++;
			}
		}
	}
	return cnt == SZ(a);
}
vector<int> adj[N];
bool art[N], vis3[N];
int low[N], t[N], curt;
void dfs(int i, int p) {
	t[i] = low[i] = curt++;
	vis3[i] = 1;
	int cnt = 0;
	for (auto nxt : adj[i]) {
		if (nxt == p) continue;
		if (vis3[nxt]) {
			low[i] = min(low[i], t[nxt]);
		} else {
			dfs(nxt, i);
			low[i] = min(low[i], low[nxt]);
			if (low[nxt] >= t[i]) {
				cnt++;
			}
		}
	}
	if (cnt > 1 || (i != p && cnt)) {
		art[i] = 1;
	}
}
vector<array<int, 2>> gud;
array<int, 2> compressed[N];
int idx[3 * N][3 * N];
int marked[3 * N][3 * N];
vector<int> vals[2];
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n;
	cin >> n;
	int type;
	cin >> type;
	vector<array<int, 3>> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i][0] >> a[i][1];
		a[i][2] = i;
		for (int k = 0; k < 2; k++) {
			vals[k].push_back(a[i][k]);
			vals[k].push_back(a[i][k] - 1);
			vals[k].push_back(a[i][k] + 1);
		}
	}
	sort(a.begin(), a.end());
	if (!check(a)) {
		cout << "NO\n";
		return 0;
	}
	for (int k = 0; k < 2; k++) {
		sort(vals[k].begin(), vals[k].end());
		vals[k].resize(unique(vals[k].begin(), vals[k].end()) - vals[k].begin());
	}
	auto getcord = [&] (int x, int y) {
		int vx = lower_bound(vals[0].begin(), vals[0].end(), x) - vals[0].begin();
		int vy = lower_bound(vals[1].begin(), vals[1].end(), y) - vals[1].begin();
		return (array<int, 2>) {vx, vy};
	};
	memset(idx, -1, sizeof idx);
	memset(marked, -1, sizeof marked);
	for (int i = 0; i < n; i++) {
		array<int, 2> cord = getcord(a[i][0], a[i][1]);
		compressed[a[i][2]] = cord;
		idx[cord[0]][cord[1]] = a[i][2];
	}
	vector<int> ans;
	while (SZ(ans) < n) {
		gud.clear();
		int pos[n]{};
		memset(pos, -1, sizeof pos);
		for (int i = 0; i < SZ(a); i++) {
			pos[a[i][2]] = i;
		}
		for (int i = 0; i < SZ(a); i++) {
			for (int k = 0; k < 8; k++) {
				gud.push_back({compressed[a[i][2]][0] + dx[k], compressed[a[i][2]][1] + dy[k]});
			}
		}
		array<int, 3> mn = {(int) 1e9 + 5, -1, -1};
		for (int k = 0; k < SZ(gud); k++) {
			vis2[k] = 0;
			mn = min(mn, (array<int, 3>) {gud[k][0], gud[k][1], k});
			marked[gud[k][0]][gud[k][1]] = k;
		}
		queue<int> q;
		q.push(mn[2]);
		vis2[mn[2]] = 1;
		while (SZ(q)) {
			int i = q.front();
			int x = gud[i][0], y = gud[i][1];
			q.pop();
			for (int k = 0; k < 4; k++) {
				int newx = x + dx[k], newy = y + dy[k];
				int nxt = -1;
				if (0 <= newx && newx < SZ(vals[0]) && 0 <= newy && newy < SZ(vals[1])) {
					if (vals[0][newx] - vals[0][x] == dx[k] && vals[1][newy] - vals[1][y] == dy[k]) {
						if (idx[newx][newy] == -1 || pos[idx[newx][newy]] == -1) {
							nxt = marked[newx][newy];
						}
					}
				}
				if (nxt != -1) {	
					q.push(nxt);
					vis2[nxt] = 1;
				}
			}
		}
		for (int i = 0; i < SZ(a); i++) {
			adj[i].clear();
			art[i] = 0;
			vis3[i] = 0;
		}
		for (int i = 0; i < SZ(a); i++) {
			int x = compressed[a[i][2]][0], y = compressed[a[i][2]][1];
			for (int k = 0; k < 8; k++) {
				int newx = x + dx[k], newy = y + dy[k];
				if (idx[newx][newy] != -1 && pos[idx[newx][newy]] != -1) {
					adj[i].push_back(pos[idx[newx][newy]]);
				}
			}
		}
		curt = 0;
		dfs(0, 0);
		array<int, 2> mx = {-1, -1};
		for (int i = 0; i < SZ(a); i++) {
			bool ok = 0;
			for (int k = 0; k < 4; k++) {
				int x = a[i][0] + dx[k], y = a[i][1] + dy[k];
				if (marked[x][y] != -1) ok |= vis2[marked[x][y]];
			}
			if (ok && !art[i]) {
				mx = max(mx, {a[i][2], i});
			}
		}
		assert(mx[0] != -1);
		ans.push_back(mx[0]);
		vector<array<int, 3>> newa;
		for (int j = 0; j < SZ(a); j++) {
			if (j == mx[1]) continue;
			newa.push_back(a[j]);
		}
		a = newa;
		for (auto [x, y] : gud) {
			marked[x][y] = -1;
		}
	}
	cout << "YES\n";
	reverse(ans.begin(), ans.end());
	for (auto i : ans) {
		cout << i + 1 << '\n';
	}
	return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 12
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20
• Subtask 6: 0 / 10
• Subtask 7: 0 / 19