oj.uz

Submission #799649

# Submission time Handle Problem Language Result Execution time Memory
799649 2023-07-31T17:57:24 Z GusterGoose27 Parking (CEOI22_parking) C++17
10 / 100
 110 ms 18196 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()) {
		cout << -1 << endl;
		exit(0);
	}
	return *avail.begin();
}

void move(int a, int b) {
	assert(config[a].size());
	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);
	}
	if (picky) return;
	int e = get_empty();
	move(p, e);
	move(p, cur);
	dfs(e, 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

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from Main.cpp:1:
Main.cpp: In function 'void move(int, int)':
Main.cpp:26:47: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   26 |  assert(config[b].empty() || config[a].back() == config[b].back()^1);
      |                              ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:69:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |   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 3 ms 5032 KB Output is correct
3 Correct 3 ms 5036 KB Output is correct
4 Correct 3 ms 5028 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct

Subtask #2
0.0 / 10.0

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

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 3 ms 5044 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 3 ms 5032 KB Output is correct
3 Correct 3 ms 5036 KB Output is correct
4 Correct 3 ms 5028 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Incorrect 110 ms 18196 KB Output isn't correct
12 Halted 0 ms 0 KB -