답안 #706814

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
706814	2023-03-07T20:30:06 Z	rainboy	Parking (CEOI22_parking)	C	50 / 100	120 ms	10704 KB

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, 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

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.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct

Subtask #2

0.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	40 ms	8908 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #3

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	300 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	292 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct

Subtask #4

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	300 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	292 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	94 ms	10500 KB	Output is correct
11	Correct	75 ms	5436 KB	Output is correct
12	Correct	48 ms	5296 KB	Output is correct
13	Correct	85 ms	9392 KB	Output is correct
14	Correct	59 ms	5468 KB	Output is correct
15	Correct	48 ms	5276 KB	Output is correct
16	Correct	105 ms	10704 KB	Output is correct
17	Correct	55 ms	5232 KB	Output is correct
18	Correct	120 ms	10144 KB	Output is correct

Subtask #5

0.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	5 ms	4052 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #6

0.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Runtime error	40 ms	8908 KB	Execution killed with signal 11
12	Halted	0 ms	0 KB	-