Submission #1213996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213996		Tob	Parking (CEOI22_parking)	C++20	100 / 100	72 ms	11964 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});
	assert(asi[x] > 0);
	assert(asi[y] < 2);
	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) {
		assert((a[y][0] ^ a[x][asi[x]-1]) == 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 z) {
	int y = a[d[x^1]][1];
	if (y == (x^1)) move(d[x], fr.front());
	else if (y == z) move(d[z], fr.front());
	else kick(y, z);
}

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--;
			a[i][0] = 2*x-2;
			a[i][1] = 2*x-1;
			asi[i] = 2;
			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);
		}
	}
	for (int i = 0; i < m; i++) if (asi[i] == 2 && a[i][0]/2 == a[i][1]/2) bio[a[i][0]/2] = 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, x);
		}
		else {
			while (ii < m && !(asi[ii] == 2 && !bio[a[ii][1]/2])) ii++;
			kick(a[ii][1], a[ii][1]);
		}
	}
	cout << res.size() << "\n";
	for (auto it : res) cout << it.F+1 << " " << it.S+1 << "\n";

	return 0;
}

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