Submission #486316


Source Code Expand

Copy
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <iostream>

using namespace std;

#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

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

int nums[101010][7];
int vptn[101010];

int trans[7][7] = {
		{ -1, 0, 1, 2, 3, 4, 5 },
		{ -1, -1, 6, 7, 8, 9, 10 },
		{ -1, -1, -1, 11, 12, 13, 14 },
		{ -1, -1, -1, -1, 15, 16, 17 },
		{ -1, -1, -1, -1, -1, 18, 19 },
		{ -1, -1, -1, -1, -1, -1, 20 },
		{ -1, -1, -1, -1, -1, -1, -1 }
};

int calc_ptn(int h)
{
	int ret = 0;
	for (int i = 0; i < W - 1; ++i) {
		int a = nums[h][i], b = nums[h][i + 1];
		if (a > b) swap(a, b);

		ret |= 1 << trans[a][b];
	}
	return ret;
}

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 Debug()
{
	for (int i = 0; i < fact[N]; ++i) {
		int pat[7];
		int2pat(i, pat);

		for (int j = 0; j < N; ++j) printf("%d ", pat[j]);
		printf(": %d\n", dist[i]);
	}
	puts("");
}

int solve(bool flg)
{
	for (int i = 0; i < W; ++i) nums[0][i] = i;
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) nums[i + 1][j] = nums[i][j];
		swap(nums[i + 1][A[i]], nums[i + 1][A[i] + 1]);
	}

	vptn[H] = calc_ptn(H);
	for (int i = H - 1; i >= 0; --i) {
		vptn[i] = vptn[i + 1] | calc_ptn(i);
	}

	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 == H || vptn[i] != vptn[i + 1] || i == 0 || vptn[i] != vptn[i - 1] || i < 100 || H - i < 100) {
			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();

			//printf("after %d\n", i);
			//Debug();
		}

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

	}

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

	return dist[target];
}

void autorun()
{
	srand(114514);
	for (;;) {
		W = 7;
		H = 5;

		for (int i = 0; i < H; ++i) A[i] = rand() % (W - 1);
		for (int i = 0; i < W; ++i) B[i] = i;

		int a = solve(false);
		int b = solve(true);

		if (a != b) {
			printf("%d %d\n", W, H);
			for (int i = 0; i < H; ++i) printf("%d ", A[i]);
			puts("");
			break;
		}
	}
}

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(H <= 200);

	return 0;
}

Submission Info

Submission Time
Task C - 天下一不正
User semiexp
Language C++11 (GCC 4.9.2)
Score 45
Code Size 4125 Byte
Status
Exec Time 2038 ms
Memory 4672 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:202: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:203: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:204: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 0 / 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 27 ms 796 KB
00_sample_2.txt 24 ms 800 KB
01_manual00.txt 27 ms 920 KB
01_manual01.txt 26 ms 804 KB
01_manual02.txt 39 ms 984 KB
01_manual03.txt 104 ms 1056 KB
01_manual04.txt 1315 ms 1064 KB
05_small100.txt 26 ms 804 KB
05_small101.txt 26 ms 800 KB
05_small102.txt 27 ms 808 KB
05_small103.txt 36 ms 808 KB
05_small104.txt 106 ms 1052 KB
05_small105.txt 26 ms 788 KB
05_small106.txt 28 ms 796 KB
05_small107.txt 42 ms 808 KB
05_small108.txt 165 ms 912 KB
05_small109.txt 1351 ms 1088 KB
05_small110.txt 700 ms 1096 KB
05_small111.txt 183 ms 1052 KB
05_small112.txt 26 ms 804 KB
05_small113.txt 28 ms 800 KB
05_small114.txt 42 ms 924 KB
05_small115.txt 165 ms 804 KB
05_small116.txt 1352 ms 1096 KB
05_small117.txt 172 ms 1048 KB
05_small118.txt 306 ms 1076 KB
05_small119.txt 372 ms 1076 KB
05_small120.txt 828 ms 1088 KB
05_small121.txt 1361 ms 1180 KB
05_small122.txt 1314 ms 1060 KB
05_small123.txt 1318 ms 1056 KB
05_small124.txt 1354 ms 1064 KB
05_small125.txt 1372 ms 1088 KB
05_small126.txt 1371 ms 1092 KB
05_small127.txt 1345 ms 1060 KB
05_small128.txt 1355 ms 1088 KB
05_small129.txt 1317 ms 1060 KB
05_small130.txt 1322 ms 1052 KB
05_small131.txt 1313 ms 1188 KB
05_small132.txt 1354 ms 1092 KB
05_small133.txt 1359 ms 1088 KB
05_small134.txt 1347 ms 1068 KB
10_large100.txt 48 ms 4256 KB
10_large101.txt 51 ms 4260 KB
10_large102.txt 81 ms 4252 KB
10_large103.txt 327 ms 4256 KB
10_large104.txt 2035 ms 4608 KB
10_large105.txt 49 ms 4264 KB
10_large106.txt 52 ms 4260 KB
10_large107.txt 80 ms 4260 KB
10_large108.txt 325 ms 4264 KB
10_large109.txt 325 ms 4368 KB
10_large110.txt 2033 ms 4624 KB
10_large111.txt 2035 ms 4604 KB
10_large112.txt 2035 ms 4624 KB
10_large113.txt 2036 ms 4568 KB
10_large114.txt 2035 ms 4608 KB
10_large115.txt 2033 ms 4568 KB
10_large116.txt 2035 ms 4616 KB
10_large117.txt 2036 ms 4600 KB
10_large118.txt 2035 ms 4596 KB
10_large119.txt 2035 ms 4624 KB
10_large120.txt 46 ms 4256 KB
10_large121.txt 52 ms 4256 KB
10_large122.txt 80 ms 4260 KB
10_large123.txt 326 ms 4260 KB
10_large124.txt 328 ms 4392 KB
10_large125.txt 2033 ms 1544 KB
10_large126.txt 327 ms 4384 KB
10_large127.txt 2036 ms 4608 KB
10_large128.txt 2035 ms 4592 KB
10_large129.txt 2035 ms 4568 KB
10_large130.txt 2035 ms 4660 KB
10_large131.txt 2038 ms 4572 KB
10_large132.txt 2035 ms 4628 KB
10_large133.txt 2035 ms 4672 KB
10_large134.txt 2036 ms 4664 KB
10_large135.txt 2034 ms 4252 KB
11_manual00.txt 2035 ms 4568 KB