oj.uz

Submission #706809

# Submission time Handle Problem Language Result Execution time Memory
706809 2023-03-07T20:09:30 Z rainboy Parking (CEOI22_parking) C
2 / 100
 44 ms 10184 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];
			else if (h2_ == -1)
				h2_ = hh[h - 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[h1];
		}
		h = h_;
	}
	return 1;
}

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

	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) % m] & 1) == 1)
			break;
	if (h2_ == -1)
		h2_ = h1_, h1_ = -1;
	move(hh[(h + 1) % m] >> 1, h2_), h2_ = -1;
	for (h_ = 0; h_ < m; h_++)
		hh_[h_] = hh[(h + 1 + h_) % m];
	hh_[m] = h2_ << 1 | 0;
	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:92:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:95:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.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 288 KB Output is correct
4 Partially correct 0 ms 340 KB Output is partially correct
5 Correct 0 ms 288 KB Output is correct
6 Correct 0 ms 288 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 288 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 10184 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 3924 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 3924 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

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 288 KB Output is correct
4 Partially correct 0 ms 340 KB Output is partially correct
5 Correct 0 ms 288 KB Output is correct
6 Correct 0 ms 288 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 288 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Runtime error 44 ms 10184 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -