Submission #1213987

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213987		Tob	Parking (CEOI22_parking)	C++20	10 / 100	30 ms	6844 KiB

Main

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

const int N = 2e5 + 7;

int n, m, nn;
int c[2*N], d[2*N], asi[N], bio[N];
int a[N][2];
queue <int> q, q2, fr;
vector <pii> res;

void move(int x, int y) {
	res.pb({x, y});
	if (!fr.empty() && fr.front() == y) fr.pop();
	if (asi[x] == 1) fr.push(x);
	else {
		c[a[x][0]] = 1;
		if (c[a[x][0]^1]) q.push(a[x][0]);
		else q2.push(a[x][0]);
	}
	if (asi[y] == 1) nn--, bio[a[y][0]/2] = 1;
	a[y][asi[y]++] = a[x][--asi[x]];
	d[a[y][asi[y]-1]] = y;
	if (asi[y] == 1 && c[a[y][0]] && c[a[y][0]^1]) q.push(a[y][0]);
}

void kick(int x) {
	int y = a[d[x^1]][1];
	if (y == (x^1)) move(d[y], fr.front());
	else kick(y);
}

int main () {
	FIO;
	cin >> n >> m;
	
	nn = n;
	for (int i = 0; i < m; i++) {
		int x, y; cin >> x >> y;
		if (x == y && x) {
			nn--;
			bio[x-1] = 1;
			continue;
		}
		x--; y--;
		if (x == -1) fr.push(i);
		if (x >= 0) x = 2*x+(bio[x]++), a[i][asi[i]++] = x, c[x] = (y == -1), d[x] = i;
		if (y >= 0) y = 2*y+(bio[y]++), a[i][asi[i]++] = y, c[y] = 1, d[y] = i;
	}
	memset(bio, 0, sizeof bio);
	for (int i = 0; i < n; i++) {
		if (c[2*i] && c[2*i+1]) {
			if (asi[d[2*i]]+asi[d[2*i+1]] < 4) q.push(asi[d[2*i]] == 1 ? 2*i : 2*i+1);
		}
	}
	int ii = 0;
	while (nn) {
		int x = -1;
		if (!q.empty()) {
			x = q.front(); q.pop();
			if (bio[x/2]) continue;
			bio[x/2] = 1;
			move(d[x^1], d[x]);
			continue;
		}
		if (fr.empty()) {
			cout << "-1\n";
			return 0;
		}
		if (!q2.empty()) {
			x = q2.front(); q2.pop();
			if (bio[x/2]) continue;
			kick(x);
		}
		else {
			while (ii < m && !(asi[ii] == 2 && !bio[a[ii][1]/2])) ii++;
			move(d[a[ii][1]], fr.front());
		}
	}
	cout << res.size() << "\n";
	for (auto it : res) cout << it.F+1 << " " << it.S+1 << "\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