Contest Duration: ~ (local time) (180 minutes)

Submission #485960

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]) {
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 2015-09-05 15:19:12+0900 C - 天下一不正 semiexp C++11 (GCC 4.9.2) 0 3633 Byte WA 246 ms 4608 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 0 / 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 23 ms 928 KB
00_sample_2.txt 24 ms 796 KB
01_manual00.txt 23 ms 932 KB
01_manual01.txt 23 ms 796 KB
01_manual02.txt 37 ms 1060 KB
01_manual03.txt 51 ms 1060 KB
01_manual04.txt 50 ms 1052 KB
05_small100.txt 23 ms 796 KB
05_small101.txt 25 ms 920 KB
05_small102.txt 25 ms 916 KB
05_small103.txt 32 ms 808 KB
05_small104.txt 77 ms 988 KB
05_small105.txt 23 ms 808 KB
05_small106.txt 24 ms 916 KB
05_small107.txt 27 ms 920 KB
05_small108.txt 41 ms 916 KB
05_small109.txt 196 ms 1080 KB
05_small110.txt 195 ms 1092 KB
05_small111.txt 104 ms 1052 KB
05_small112.txt 23 ms 924 KB
05_small113.txt 25 ms 920 KB
05_small114.txt 24 ms 928 KB
05_small115.txt 38 ms 800 KB
05_small116.txt 207 ms 1080 KB
05_small117.txt 118 ms 1056 KB
05_small118.txt 209 ms 1092 KB
05_small119.txt 155 ms 1064 KB
05_small120.txt 195 ms 1088 KB
05_small121.txt 195 ms 1080 KB
05_small122.txt 49 ms 1060 KB
05_small123.txt 49 ms 1064 KB
05_small124.txt 51 ms 992 KB
05_small125.txt 181 ms 1092 KB
05_small126.txt 194 ms 1076 KB
05_small127.txt 91 ms 1056 KB
05_small128.txt 181 ms 1076 KB
05_small129.txt 49 ms 1184 KB
05_small130.txt 51 ms 1072 KB
05_small131.txt 49 ms 1064 KB
05_small132.txt 207 ms 1092 KB
05_small133.txt 196 ms 1076 KB
05_small134.txt 101 ms 1060 KB
10_large100.txt 46 ms 4260 KB
10_large101.txt 46 ms 4260 KB
10_large102.txt 46 ms 4264 KB
10_large103.txt 59 ms 4388 KB
10_large104.txt 229 ms 4592 KB
10_large105.txt 46 ms 4264 KB
10_large106.txt 46 ms 4256 KB
10_large107.txt 48 ms 4256 KB
10_large108.txt 47 ms 4264 KB
10_large109.txt 66 ms 4380 KB
10_large110.txt 246 ms 4588 KB
10_large111.txt 234 ms 4592 KB
10_large112.txt 232 ms 4592 KB
10_large113.txt 70 ms 4512 KB
10_large114.txt 179 ms 4596 KB
10_large115.txt 73 ms 4516 KB
10_large116.txt 245 ms 4596 KB
10_large117.txt 233 ms 4588 KB
10_large118.txt 234 ms 4584 KB
10_large119.txt 244 ms 4592 KB
10_large120.txt 44 ms 4248 KB
10_large121.txt 47 ms 4268 KB
10_large122.txt 49 ms 4252 KB
10_large123.txt 46 ms 4260 KB
10_large124.txt 59 ms 4312 KB
10_large125.txt 224 ms 1424 KB
10_large126.txt 60 ms 4388 KB
10_large127.txt 218 ms 4600 KB
10_large128.txt 231 ms 4608 KB
10_large129.txt 71 ms 4524 KB
10_large130.txt 86 ms 4572 KB
10_large131.txt 73 ms 4516 KB
10_large132.txt 126 ms 4568 KB
10_large133.txt 230 ms 4588 KB
10_large134.txt 230 ms 4596 KB
10_large135.txt 217 ms 4264 KB
11_manual00.txt 72 ms 4508 KB