Submission #946434

#	Time	Username	Problem	Language	Result	Execution time	Memory
946434		MinaRagy06	Parking (CEOI22_parking)	C++17	10 / 100	2079 ms	524288 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long

vector<array<int, 2>> v;
set<vector<array<int, 2>>> vis;
int cur = 0, mn = 1e9;
int n, m;
pair<int, vector<array<int, 2>>> solve() {
	queue<pair<pair<int, vector<array<int, 2>>>, vector<array<int, 2>>>> q;
	q.push({{0, {}}, v});
	while (q.size()) {
		int c = q.front().first.first;
		vector<array<int, 2>> ops = q.front().first.second;
		vector<array<int, 2>> v = q.front().second;
		q.pop();
		bool gud = 1;
		for (auto [b, t] : v) {
			gud &= b == t;
		}
		if (gud) {
			return {c, ops};
		}
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < m; j++) {
				if (i == j) continue;
				if (!v[i][0] || v[j][1] || (v[i][0] && v[i][0] == v[i][1]) || (v[j][0] && v[j][0] == v[j][1])) continue;
				int x = 1, y = 0;
				if (!v[i][x]) x = 0;
				if (v[j][y]) y = 1;
				if (y == 0 || v[i][x] == v[j][0]) {
					swap(v[i][x], v[j][y]);
					cur++;
					ops.push_back({i + 1, j + 1});
					if (vis.find(v) == vis.end()) {
						vis.insert(v);
						q.push({{c + 1, ops}, v});
					}
					ops.pop_back();
					cur--;
					swap(v[i][x], v[j][y]);
				}
			}
		}
	}
	return {1e9, {}};
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	v.resize(m);
	for (int i = 0; i < m; i++) {
		cin >> v[i][0] >> v[i][1];
	}
	pair<int, vector<array<int, 2>>> ans = solve();
	if (ans.first == (int)1e9) {
		cout << "-1\n";
	} else {
		vector<array<int, 2>> ops = ans.second;
		cout << ops.size() << '\n';
		for (auto [x, y] : ops) {
			cout << x << ' ' << y << '\n';
		}
	}
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 15
• Subtask 5: 0 / 25
• Subtask 6: 0 / 15