Submission #706816

#	Time	Username	Problem	Language	Result	Execution time	Memory
706816		rainboy	Parking (CEOI22_parking)	C11	100 / 100	115 ms	11528 KiB

Main

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	200000
#define M	200000

int ij[M * 2], eh[N][2], eo[N]; int *hhh[N], mm[N], n_, h1_, h2_;
int hh1[N * 2], hh2[N * 2], cnt;

void move(int h1, int h2) {
	int i;

	hh1[cnt] = h1, hh2[cnt] = h2, cnt++;
	if (ij[h1 << 1 | 1] != -1)
		i = ij[h1 << 1 | 1], ij[h1 << 1 | 1] = -1;
	else
		i = ij[h1 << 1 | 0], ij[h1 << 1 | 0] = -1;
	if (ij[h2 << 1 | 0] == -1)
		ij[h2 << 1 | 0] = i;
	else
		ij[h2 << 1 | 1] = i;
}

int solve1(int *hh, int m) {
	int h, h_, h1;

	if (h1_ == -1) {
		h = 0;
		while (h < m && (hh[h] & 1) == 1)
			h++;
		while (h < m && (hh[h] & 1) == 0)
			h++;
		if (h < m)
			return 0;
	}
	h = 0;
	while (1) {
		h_ = h;
		while (h_ < m && (hh[h_] & 1) == 1)
			h_++;
		for (h1 = h + 1; h1 < h_; h1++)
			move(hh[h1] >> 1, hh[h1 - 1] >> 1);
		h = h_;
		while (h_ < m && (hh[h_] & 1) == 0)
			h_++;
		if (h_ == m) {
			for (h1 = h_ - 1; h1 >= h; h1--)
				move(hh[h1 - 1] >> 1, hh[h1] >> 1);
			if (h1_ == -1)
				h1_ = hh[h - 1] >> 1;
			else if (h2_ == -1)
				h2_ = hh[h - 1] >> 1;
			break;
		} else {
			move(hh[h_] >> 1, h1_);
			move(hh[h_ - 1] >> 1, h1_);
			for (h1 = h_ - 1; h1 >= h; h1--)
				move(hh[h1 - 1] >> 1, hh[h1] >> 1);
			h1_ = hh[h - 1] >> 1;
		}
		h = h_;
	}
	return 1;
}

int solve2(int *hh, int m) {
	static int hh_[N + 1];
	int h, h_, tmp;

	if (m == 1)
		return 1;
	if (h1_ == -1)
		return 0;
	for (h = 0; h + 1 < m; h++)
		if ((hh[h] & 1) == 0 && (hh[h + 1] & 1) == 1)
			break;
	if (h2_ == -1)
		h2_ = h1_, h1_ = -1;
	move(hh[(h + 1) % m] >> 1, h2_);
	for (h_ = 0; h_ < m; h_++)
		hh_[h_] = hh[(h + 1 + h_) % m];
	hh_[m] = h2_ << 1 | 0;
	h2_ = -1;
	if ((hh_[0] & 1) == 0) {
		tmp = hh_[0], hh_[0] = hh_[m], hh_[m] = tmp;
		hh_[0] ^= 1;
	}
	return solve1(hh_, m + 1);
}

int main() {
	static char visited[N];
	static int hh[N + 1];
	int n, m, m_, g, h, h_, i, j, good;

	scanf("%d%d", &n, &m);
	h1_ = h2_ = -1;
	for (h = 0; h < m; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		ij[h << 1 | 0] = i, ij[h << 1 | 1] = j;
		if (i != -1)
			eh[i][eo[i]++] = h << 1 | 0;
		if (j != -1)
			eh[j][eo[j]++] = h << 1 | 1;
		if (i == -1) {
			if (h1_ == -1)
				h1_ = h;
			else if (h2_ == -1)
				h2_ = h;
		}
	}
	for (h = 0; h < m; h++)
		if (ij[h << 1 | 1] == -1 && ij[h << 1 | 0] != -1 && !visited[ij[h << 1 | 0]]) {
			m_ = 0;
			for (h_ = h << 1 | 1; (i = ij[h_ ^ 1]) != -1; h_ ^= eh[i][0] ^ eh[i][1] ^ 1)
				hh[m_++] = h_, visited[i] = 1;
			hh[m_++] = h_;
			hhh[n_] = (int *) malloc((mm[n_] = m_) * sizeof *hhh[n_]);
			memcpy(hhh[n_], hh, m_ * sizeof *hh), n_++;
		}
	if (n_ > 0) {
		good = 0;
		for (i = 0; i < n_; i++)
			if (solve1(hhh[i], mm[i])) {
				good = 1;
				for (j = 0; j < n_; j++)
					if (j != i)
						solve1(hhh[j], mm[j]);
				break;
			}
		if (!good) {
			printf("-1\n");
			return 0;
		}
	}
	for (i = 0; i < n; i++)
		if (!visited[i]) {
			h = eh[i][0];
			m_ = 0;
			for (h_ = h; (j = ij[h_ ^ 1]) != i; h_ ^= eh[j][0] ^ eh[j][1] ^ 1)
				hh[m_++] = h_, visited[j] = 1;
			hh[m_++] = h_, visited[i] = 1;
			if (!solve2(hh, m_)) {
				printf("-1\n");
				return 0;
			}
		}
	printf("%d\n", cnt);
	for (g = 0; g < cnt; g++)
		printf("%d %d\n", hh1[g] + 1, hh2[g] + 1);
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:97:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:100:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

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