Submission #486685


Source Code Expand

Copy
#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

int W, H, N;
int A[101010];
int B[7];

int dist[5040], dtmp[5040]; bool vis[5040];
int from[7];
int fact[] = { 1, 1, 2, 6, 24, 120, 720, 5040 };

int pat2int(int* v)
{
	bool used[7];
	for (int i = 0; i < N; ++i) used[i] = false;

	int ret = 0;
	for (int i = 0; i < N; ++i) {
		int c = 0;
		for (int j = 0; j < v[i]; ++j) if (!used[j]) ++c;
		ret += c * fact[N - 1 - i];
		used[v[i]] = true;
	}
	return ret;
}

void int2pat(int v, int* sto)
{
	bool used[7];
	for (int i = 0; i < N; ++i) used[i] = false;

	for (int i = 0; i < N; ++i) {
		int at = v / fact[N - 1 - i];
		for (int j = 0; j < N; ++j) {
			if (!used[j] && at-- == 0) {
				used[j] = true;
				sto[i] = j;
				break;
			}
		}
		v %= fact[N - 1 - i];
	}
}

void do_movs()
{
	for (int i = 0; i < fact[N]; ++i) vis[i] = false;

	priority_queue<pair<int, int> > Q;
	for (int i = 0; i < fact[N]; ++i) {
		Q.push(make_pair(-dist[i], i));
	}

	int ary[7];

	while (!Q.empty()) {
		pair<int, int> tmp = Q.top(); Q.pop();

		int loc = tmp.second, cost = -tmp.first;
		if (vis[loc]) continue;
		vis[loc] = true;

		if (dist[loc] > cost) {
			dist[loc] = cost;
		}

		int2pat(loc, ary);

		for (int i = 0; i < N - 1; ++i) {
			swap(ary[i], ary[i + 1]);
			int p2 = pat2int(ary);
			Q.push(make_pair(-(cost + 1), p2));
			swap(ary[i], ary[i + 1]);
		}
	}
}

void solve()
{
	for (int i = 0; i < W; ++i) from[i] = i;
	for (int i = 0; i < fact[N]; ++i) dist[i] = 100000;
	dist[0] = 0;

	for (int i = 0; i <= H; ++i) {
		if (i < 50 || H - i < 50) {
			for (int j = 0; j < fact[N]; ++j) {
				int ary[7], trans[7];
				int2pat(j, (int*)ary);

				for (int k = 0; k < N; ++k) trans[k] = ary[from[k]];
				dtmp[pat2int((int*)trans)] = dist[j];
			}
			for (int j = 0; j < N; ++j) from[j] = j;

			for (int j = 0; j < fact[N]; ++j) dist[j] = dtmp[j];

			do_movs();
		}

		if (i != H)
			swap(from[A[i]], from[A[i] + 1]);
	}

	int target = pat2int(B);
	printf("%d\n", dist[target]);
}

int main()
{
	scanf("%d%d", &W, &H); N = W;
	for (int i = 0; i < H; ++i) scanf("%d", A + i); 
	for (int i = 0; i < W; ++i) scanf("%d", B + i);

	solve();

	return 0;
}

Submission Info

Submission Time
Task C - 天下一不正
User semiexp
Language C++11 (GCC 4.9.2)
Score 150
Code Size 2294 Byte
Status
Exec Time 1356 ms
Memory 1464 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:113:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &W, &H); N = W;
                       ^
./Main.cpp:114:48: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < H; ++i) scanf("%d", A + i); 
                                                ^
./Main.cpp:115:48: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < W; ++i) scanf("%d", B + i);
                                                ^

Judge Result

Set Name Score / Max Score Test Cases
small 45 / 45 00_sample_1.txt, 00_sample_2.txt, 01_manual00.txt, 01_manual01.txt, 01_manual02.txt, 01_manual03.txt, 01_manual04.txt, 05_small100.txt, 05_small101.txt, 05_small102.txt, 05_small103.txt, 05_small104.txt, 05_small105.txt, 05_small106.txt, 05_small107.txt, 05_small108.txt, 05_small109.txt, 05_small110.txt, 05_small111.txt, 05_small112.txt, 05_small113.txt, 05_small114.txt, 05_small115.txt, 05_small116.txt, 05_small117.txt, 05_small118.txt, 05_small119.txt, 05_small120.txt, 05_small121.txt, 05_small122.txt, 05_small123.txt, 05_small124.txt, 05_small125.txt, 05_small126.txt, 05_small127.txt, 05_small128.txt, 05_small129.txt, 05_small130.txt, 05_small131.txt, 05_small132.txt, 05_small133.txt, 05_small134.txt
All 105 / 105 00_sample_1.txt, 00_sample_2.txt, 01_manual00.txt, 01_manual01.txt, 01_manual02.txt, 01_manual03.txt, 01_manual04.txt, 05_small100.txt, 05_small101.txt, 05_small102.txt, 05_small103.txt, 05_small104.txt, 05_small105.txt, 05_small106.txt, 05_small107.txt, 05_small108.txt, 05_small109.txt, 05_small110.txt, 05_small111.txt, 05_small112.txt, 05_small113.txt, 05_small114.txt, 05_small115.txt, 05_small116.txt, 05_small117.txt, 05_small118.txt, 05_small119.txt, 05_small120.txt, 05_small121.txt, 05_small122.txt, 05_small123.txt, 05_small124.txt, 05_small125.txt, 05_small126.txt, 05_small127.txt, 05_small128.txt, 05_small129.txt, 05_small130.txt, 05_small131.txt, 05_small132.txt, 05_small133.txt, 05_small134.txt, 10_large100.txt, 10_large101.txt, 10_large102.txt, 10_large103.txt, 10_large104.txt, 10_large105.txt, 10_large106.txt, 10_large107.txt, 10_large108.txt, 10_large109.txt, 10_large110.txt, 10_large111.txt, 10_large112.txt, 10_large113.txt, 10_large114.txt, 10_large115.txt, 10_large116.txt, 10_large117.txt, 10_large118.txt, 10_large119.txt, 10_large120.txt, 10_large121.txt, 10_large122.txt, 10_large123.txt, 10_large124.txt, 10_large125.txt, 10_large126.txt, 10_large127.txt, 10_large128.txt, 10_large129.txt, 10_large130.txt, 10_large131.txt, 10_large132.txt, 10_large133.txt, 10_large134.txt, 10_large135.txt, 11_manual00.txt
Case Name Status Exec Time Memory
00_sample_1.txt 25 ms 800 KB
00_sample_2.txt 25 ms 932 KB
01_manual00.txt 23 ms 800 KB
01_manual01.txt 25 ms 920 KB
01_manual02.txt 41 ms 936 KB
01_manual03.txt 99 ms 940 KB
01_manual04.txt 1277 ms 936 KB
05_small100.txt 25 ms 800 KB
05_small101.txt 23 ms 928 KB
05_small102.txt 24 ms 924 KB
05_small103.txt 34 ms 932 KB
05_small104.txt 100 ms 1056 KB
05_small105.txt 23 ms 928 KB
05_small106.txt 25 ms 796 KB
05_small107.txt 39 ms 924 KB
05_small108.txt 157 ms 928 KB
05_small109.txt 1314 ms 1068 KB
05_small110.txt 682 ms 1080 KB
05_small111.txt 177 ms 1044 KB
05_small112.txt 24 ms 924 KB
05_small113.txt 27 ms 804 KB
05_small114.txt 39 ms 796 KB
05_small115.txt 158 ms 800 KB
05_small116.txt 1318 ms 1072 KB
05_small117.txt 167 ms 1036 KB
05_small118.txt 321 ms 1068 KB
05_small119.txt 360 ms 1048 KB
05_small120.txt 809 ms 1068 KB
05_small121.txt 1307 ms 1068 KB
05_small122.txt 1275 ms 928 KB
05_small123.txt 1277 ms 928 KB
05_small124.txt 1274 ms 1060 KB
05_small125.txt 1312 ms 1064 KB
05_small126.txt 1311 ms 1072 KB
05_small127.txt 1327 ms 1040 KB
05_small128.txt 1312 ms 1068 KB
05_small129.txt 1275 ms 932 KB
05_small130.txt 1274 ms 932 KB
05_small131.txt 1274 ms 936 KB
05_small132.txt 1308 ms 1072 KB
05_small133.txt 1312 ms 1064 KB
05_small134.txt 1298 ms 1048 KB
10_large100.txt 37 ms 1188 KB
10_large101.txt 40 ms 1192 KB
10_large102.txt 51 ms 1188 KB
10_large103.txt 172 ms 1188 KB
10_large104.txt 1320 ms 1460 KB
10_large105.txt 39 ms 1196 KB
10_large106.txt 40 ms 1188 KB
10_large107.txt 54 ms 1196 KB
10_large108.txt 171 ms 1192 KB
10_large109.txt 171 ms 1188 KB
10_large110.txt 1322 ms 1460 KB
10_large111.txt 1356 ms 1456 KB
10_large112.txt 1326 ms 1452 KB
10_large113.txt 1290 ms 1308 KB
10_large114.txt 1321 ms 1460 KB
10_large115.txt 1288 ms 1308 KB
10_large116.txt 1325 ms 1452 KB
10_large117.txt 1342 ms 1448 KB
10_large118.txt 1326 ms 1464 KB
10_large119.txt 1323 ms 1456 KB
10_large120.txt 39 ms 1108 KB
10_large121.txt 40 ms 1192 KB
10_large122.txt 54 ms 1184 KB
10_large123.txt 173 ms 1188 KB
10_large124.txt 171 ms 1180 KB
10_large125.txt 1310 ms 1104 KB
10_large126.txt 171 ms 1184 KB
10_large127.txt 1320 ms 1452 KB
10_large128.txt 1350 ms 1460 KB
10_large129.txt 1302 ms 1376 KB
10_large130.txt 1320 ms 1428 KB
10_large131.txt 1314 ms 1368 KB
10_large132.txt 1330 ms 1432 KB
10_large133.txt 1353 ms 1452 KB
10_large134.txt 1322 ms 1456 KB
10_large135.txt 1322 ms 1420 KB
11_manual00.txt 1290 ms 1312 KB