oj.uz

Submission #799660

# Submission time Handle Problem Language Result Execution time Memory
799660 2023-07-31T18:09:38 Z GusterGoose27 Parking (CEOI22_parking) C++17
20 / 100
 87 ms 18972 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5+5;
int n, m;
vector<int> config[MAXN];
int inv[2*MAXN]; // 2*i+0 for bottom 1 for top
bool vis[MAXN];

typedef pair<int, int> pii;

vector<pii> res;
set<int> avail;

int get_empty() {
	if (avail.empty()) {
		// assert(false);
		cout << -1 << endl;
		exit(0);
	}
	return *avail.begin();
}

void move(int a, int b) {
	assert(config[a].size());
	assert(config[b].size() < 2);
	assert(config[b].empty() || config[a].back() == (config[b].back()^1));

	res.push_back(pii(a+1, b+1));
	if (config[b].empty()) avail.erase(b);
	config[b].push_back(config[a].back());
	config[a].pop_back();
	if (config[a].empty()) avail.insert(a);
	inv[config[b].back()] = 2*b+config[b].size()-1;
}

void dfs(int cur, bool picky = 0) {
	int v = config[cur][0];
	int p = inv[v^1]/2;
	if (config[p].size() == 1) {
		move(p, cur);
		return;
	}
	if (inv[v^1]&1) {
		move(p, cur);
		return dfs(p, picky);
	}
	int s = p;
	vector<pii> qu;
	while (config[s].size() == 2 && !(inv[config[s][1]^1] & 1)) {
		int nxt = inv[config[s][1]^1]/2;
		qu.push_back(pii(s, nxt));
		s = nxt;
	}
	if (config[s].size() == 2) {
		if (picky) return;
		int e = get_empty();
		move(s, e);
		s = e;
	}
	for (int i = qu.size()-1; i >= 0; i--) move(qu[i].first, qu[i].second);
	move(p, cur);
	if (config[s].size() == 1) dfs(s, picky);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y; cin >> x >> y;
		if (x > 0) {
			config[i].push_back(2*(x-1)+vis[x-1]);
			vis[x-1] = 1;
		}
		if (y > 0) {
			config[i].push_back(2*(y-1)+vis[y-1]);
			vis[y-1] = 1;
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < config[i].size(); j++) {
			inv[config[i][j]] = 2*i+j;
		}
		if (config[i].empty()) avail.insert(i);
	}
	// first step: combine single bottoms (we do this first because it frees space for free)
	// we aren't using compression, so we will have to explicitly check for each single bottom whether it is linked
	for (int i = 0; i < m; i++) {
		if (config[i].size() == 1) {
			dfs(i, 1);
		}
	}

	// now, for each single bottom, combine it (again, this frees space).
	// this will always take exactly 1 empty spot, so this is the best option
	for (int i = 0; i < m; i++) {
		if (config[i].size() == 1) {
			dfs(i);
		}
	}
	// nothing else will free up space, so order no longer matters
	for (int i = 0; i < m; i++) {
		if (config[i].empty()) continue;
		assert(config[i].size() == 2);
		if (config[i][0] == (config[i][1]^1)) continue;
		int e = get_empty();
		move(i, e);
		dfs(i, 0);
	}
	for (int i = 0; i < m; i++) assert(config[i].empty() || (config[i].size() == 2 && (config[i][0]^1) == config[i][1]));
	cout << res.size() << '\n';
	for (pii p: res) {
		cout << p.first << ' ' << p.second << '\n';
	}
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:82:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   for (int j = 0; j < config[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 4928 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 16844 KB Output is correct
2 Correct 87 ms 18672 KB Output is correct
3 Correct 78 ms 17372 KB Output is correct
4 Correct 72 ms 17348 KB Output is correct
5 Correct 87 ms 18972 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 4928 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 79 ms 16844 KB Output is correct
12 Correct 87 ms 18672 KB Output is correct
13 Correct 78 ms 17372 KB Output is correct
14 Correct 72 ms 17348 KB Output is correct
15 Correct 87 ms 18972 KB Output is correct
16 Incorrect 2 ms 5076 KB Output isn't correct
17 Halted 0 ms 0 KB -