oj.uz

Submission #946434

# Submission time Handle Problem Language Result Execution time Memory
946434 2024-03-14T16:27:56 Z MinaRagy06 Parking (CEOI22_parking) C++17
10 / 100
 2000 ms 524288 KB 
#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.0 / 10.0

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

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 247 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2033 ms 490572 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2033 ms 490572 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2079 ms 492896 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Runtime error 247 ms 524288 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -