Submission #485966


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 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);

	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] || true) {
			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 0;
}

Submission Info

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

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:133: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:134: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:135: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 25 ms 800 KB
00_sample_2.txt 23 ms 924 KB
01_manual00.txt 24 ms 796 KB
01_manual01.txt 26 ms 732 KB
01_manual02.txt 38 ms 1172 KB
01_manual03.txt 104 ms 988 KB
01_manual04.txt 1309 ms 1052 KB
05_small100.txt 26 ms 924 KB
05_small101.txt 25 ms 912 KB
05_small102.txt 28 ms 796 KB
05_small103.txt 34 ms 924 KB
05_small104.txt 104 ms 1176 KB
05_small105.txt 25 ms 924 KB
05_small106.txt 27 ms 920 KB
05_small107.txt 40 ms 924 KB
05_small108.txt 163 ms 924 KB
05_small109.txt 1351 ms 1088 KB
05_small110.txt 692 ms 1084 KB
05_small111.txt 181 ms 1064 KB
05_small112.txt 26 ms 796 KB
05_small113.txt 27 ms 924 KB
05_small114.txt 42 ms 924 KB
05_small115.txt 164 ms 920 KB
05_small116.txt 1350 ms 1096 KB
05_small117.txt 171 ms 1068 KB
05_small118.txt 300 ms 1080 KB
05_small119.txt 367 ms 1072 KB
05_small120.txt 826 ms 1092 KB
05_small121.txt 1347 ms 1100 KB
05_small122.txt 1311 ms 1056 KB
05_small123.txt 1309 ms 1056 KB
05_small124.txt 1318 ms 1060 KB
05_small125.txt 1350 ms 1092 KB
05_small126.txt 1353 ms 1088 KB
05_small127.txt 1337 ms 1068 KB
05_small128.txt 1347 ms 1088 KB
05_small129.txt 1307 ms 988 KB
05_small130.txt 1306 ms 1176 KB
05_small131.txt 1309 ms 1056 KB
05_small132.txt 1349 ms 1180 KB
05_small133.txt 1362 ms 1088 KB
05_small134.txt 1333 ms 1068 KB
10_large100.txt 267 ms 4256 KB
10_large101.txt 1711 ms 4268 KB
10_large102.txt 2034 ms 4388 KB
10_large103.txt 2033 ms 4388 KB
10_large104.txt 2033 ms 4608 KB
10_large105.txt 267 ms 4264 KB
10_large106.txt 1709 ms 4260 KB
10_large107.txt 2034 ms 4388 KB
10_large108.txt 2033 ms 4440 KB
10_large109.txt 2035 ms 4380 KB
10_large110.txt 2034 ms 4600 KB
10_large111.txt 2035 ms 4608 KB
10_large112.txt 2034 ms 4608 KB
10_large113.txt 2034 ms 4572 KB
10_large114.txt 2034 ms 4664 KB
10_large115.txt 2033 ms 4624 KB
10_large116.txt 2034 ms 4652 KB
10_large117.txt 2033 ms 4728 KB
10_large118.txt 2034 ms 4600 KB
10_large119.txt 2034 ms 4616 KB
10_large120.txt 265 ms 4252 KB
10_large121.txt 1713 ms 4312 KB
10_large122.txt 2034 ms 4388 KB
10_large123.txt 2033 ms 4392 KB
10_large124.txt 2034 ms 4516 KB
10_large125.txt 2033 ms 1456 KB
10_large126.txt 2035 ms 4508 KB
10_large127.txt 2035 ms 4632 KB
10_large128.txt 2034 ms 4596 KB
10_large129.txt 2035 ms 4564 KB
10_large130.txt 2034 ms 4652 KB
10_large131.txt 2033 ms 4576 KB
10_large132.txt 2033 ms 4580 KB
10_large133.txt 2034 ms 4672 KB
10_large134.txt 2033 ms 4600 KB
10_large135.txt 2035 ms 4352 KB
11_manual00.txt 2035 ms 4568 KB