Submission #72125078

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
int n, m;
int pos[16];
int encode_status(const int status[]) {
  int res = 0;
  int i;
  for (i = 0; i < n; i++) {
    res = res * 3 + status[i];
  }
  return res;
}
void decode_status(int status[], int status_id) {
  int i;
  for (i = n - 1; i >= 0; i--) {
    status[i] = status_id % 3;
    status_id /= 3;
  }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

int n, m;
int pos[16];

int encode_status(const int status[]) {
	int res = 0;
	int i;
	for (i = 0; i < n; i++) {
		res = res * 3 + status[i];
	}
	return res;
}

void decode_status(int status[], int status_id) {
	int i;
	for (i = n - 1; i >= 0; i--) {
		status[i] = status_id % 3;
		status_id /= 3;
	}
}

const int from[4] = { 0, 1, 1, 2 }, to[4] = { 1, 0, 2, 1 };

#define INF 1010101010

/* 3**15 = 14348907 */
#define MAX 21234567
int q[MAX];
int mincost[MAX];

int main(void) {
	int i;
	int start_id;
	int qs = 0, qe = 0;
	if (scanf("%d%d", &n, &m) != 2) return 1;
	for (i = 0; i < 3; i++) {
		int num, j;
		if (scanf("%d", &num) != 1) return 1;
		for (j = 0; j < num; j++) {
			int koppu;
			if (scanf("%d", &koppu) != 1) return 1;
			pos[koppu - 1] = i;
		}
	}
	for (i = 0; i < MAX; i++) mincost[i] = INF;
	start_id = encode_status(pos);
	q[qe++] = start_id;
	mincost[start_id] = 0;
	while (qs < qe) {
		int cur = q[qs++];
		int cur_status[16];
		int cur_max[3] = { -1, -1, -1 };
		decode_status(cur_status, cur);
		for (i = 0; i < n; i++) {
			cur_max[cur_status[i]] = i;
		}
		if (cur_max[1] < 0 && (cur_max[0] < 0 || cur_max[2] < 0)) {
			printf("%d\n", mincost[cur] <= m ? mincost[cur] : -1);
			return 0;
		}
		for (i = 0; i < 4; i++) {
			if (cur_max[from[i]] > cur_max[to[i]]) {
				int next;
				cur_status[cur_max[from[i]]] = to[i];
				next = encode_status(cur_status);
				if (mincost[next] > mincost[cur] + 1) {
					mincost[next] = mincost[cur] + 1;
					q[qe++] = next;
				}
				cur_status[cur_max[from[i]]] = from[i];
			}
		}
	}
	puts("-1");
	return 0;
}

Submission Info

Judge Result