### Andrew Stankevich’s Contest #11解题报告 » ZOJ3371

ZOJ3371.cpp

```// #include <map>
#include <ext/hash_map>
#include <string>
#include <vector>
#include <cstdio>
#include <algorithm>

using namespace std;
using namespace __gnu_cxx;

typedef vector<char> VI;

namespace __gnu_cxx {
template<>
struct hash<VI> {
size_t operator()(const VI& v) const {
size_t ret = 0;
for (VI::const_iterator i = v.begin(); i != v.end(); ++i) {
ret = ret * 37 + *i;
}
return ret;
}
};
};

typedef hash_map<VI, string> MVI;

int main() {
int n, q, p, x;
int m[12], l[12];
VI vs, vt;

while (scanf("%d%d%d", &n, &q, &p) != EOF) {
vs.resize(n);
vt.resize(n);
for (int i = 0; i < n; ++i) {
scanf("%d", &x);
vs[i] = x - 1;
}
for (int i = 0; i < n; ++i) {
scanf("%d", &x);
vt[i] = x - 1;
}
for (int i = 0; i < p; ++i) {
scanf("%d%d", &l[i], &m[i]);
l[i] = n - l[i];
m[i] = l[i] - m[i];
}

// forward
MVI s;
s[vs] = "";
for (int i = 0; i < q / 2; ++i) {
MVI tmp;
for (MVI::const_iterator j = s.begin(); j != s.end(); ++j) {
for (int k = 0; k < p; ++k) {
VI v(j->first);
rotate(v.begin(), v.begin() + m[k], v.begin() + l[k]);
tmp[v] = j->second + (char)('1' + k);
}
}
s.swap(tmp);
}
fprintf(stderr, "%d ", (int)s.size());

// backward
MVI t;
t[vt] = "";
for (int i = 0; i < p; ++i) {
m[i] = l[i] - m[i];
}
for (int i = 0; i < (q + 1) / 2; ++i) {
MVI tmp;
for (MVI::const_iterator j = t.begin(); j != t.end(); ++j) {
for (int k = 0; k < p; ++k) {
VI v(j->first);
rotate(v.begin(), v.begin() + m[k], v.begin() + l[k]);
tmp[v] = j->second + (char)('1' + k);
}
}
t.swap(tmp);
}
fprintf(stderr, "%d\n", (int)t.size());

//
string ans = "";
for (MVI::const_iterator i = s.begin(); i != s.end(); ++i) {
if (t.count(i->first) > 0) {
ans = i->second + string(t[i->first].rbegin(), t[i->first].rend());
}
}
if (ans == "") {
puts("Impossible");
} else {
for (int i = 0; i < q; ++i) {
printf("%c%c", ans[i], i == q - 1 ? '\n' : ' ');
}
}
}

return 0;
}

//real	0m11.372s
//user	0m10.909s
//sys	0m0.412s

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin
//182 	2010-07-08 14:43:57 	Accepted 	asc11j 	C++ 	17860 	53732 	watashi@Zodiac 	Source
```
One Response to “ZOJ3371”
1. duolon says:

ORZ，神级代码。

2.