oj.uz

Submission #706814

# Submission time Handle Problem Language Result Execution time Memory
706814 2023-03-07T20:30:06 Z rainboy Parking (CEOI22_parking) C
50 / 100
 120 ms 10704 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -