1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
| #include <algorithm>
#include <climits>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>
using namespace std;
typedef vector<int> vi;
const int N = 81;
int n, mem[N][N][N];
basic_string<int> res, se, sh, sl, su;
int compute(int ne, int nh, int nl, int nu, bool flag)
{
if (ne == n || nh+nl == 1 && ne == n-1)
return 0;
int &ret = mem[nh][nl][nu];
if (ret) return ret;
ret = INT_MAX/2;
for (int lh = 0; lh <= nh; ++lh)
for (int ll = 0; ll <= nl; ++ll)
for (int lu = 0; lu <= nu && lh+ll+lu <= n/2; ++lu)
for (int rh = 0; rh <= nh-lh; ++rh)
for (int rl = 0; rl <= nl-ll; ++rl)
for (int ru = 0; ru <= nu-lu; ++ru)
if (lh+ll+lu >= rh+rl+ru)
{
int re = lh+ll+lu-rh-rl-ru;
if (re > ne) continue;
int t = max(max(
compute(n-lh-lu-rl-ru, lh+lu, rl+ru, 0, false)+1,
compute(n-rh-ru-ll-lu, rh+ru, ll+lu, 0, false)+1),
compute(ne+lh+ll+lu+rh+rl+ru, nh-lh-rh, nl-ll-rl, nu-lu-ru, false)+1);
if (flag && t < ret)
{
basic_string<int> s1 = sh.substr(0, lh)+sl.substr(0, ll)+su.substr(0, lu),
s2 = sh.substr(lh, rh)+sl.substr(ll, rl)+su.substr(lu, ru)+se.substr(0, re);
sort(s1.begin(), s1.end());
sort(s2.begin(), s2.end());
res = s1;
res.push_back(-1);
res += s2;
}
ret = min(ret, t);
}
return ret;
}
bool solve(vector<vi> left, vector<vi> right, string result)
{
vi p(n, 3);
for (int i = 0; i < left.size(); ++i)
if (result[i] == 'E')
{
for (auto it = left[i].begin(); it != left[i].end(); ++it)
p[*it] = 0;
for (auto it = right[i].begin(); it != right[i].end(); ++it)
p[*it] = 0;
}
else
{
if (result[i] == 'R') left[i].swap(right[i]);
for (auto it = left[i].begin(); it != left[i].end(); ++it)
p[*it] &= ~2;
for (auto it = right[i].begin(); it != right[i].end(); ++it)
p[*it] &= ~1;
for (int j = 0; j < n; ++j)
if (find(left[i].begin(), left[i].end(), j) == left[i].end()
&& find(right[i].begin(), right[i].end(), j) == right[i].end())
p[j] = 0;
}
for (int i = 0; i < n; ++i)
switch (p[i])
{
case 0: se.push_back(i); break;
case 1: sh.push_back(i); break;
case 2: sl.push_back(i); break;
case 3: su.push_back(i);
}
if (se.size() == n) return false;
compute(se.size(), sh.size(), sl.size(), su.size(), true);
return true;
}
int main()
{
int m;
string result;
vector<vi> left, right;
cin >> n >> m;
while (m--)
{
char op;
int num, x;
vi L, R;
cin >> num;
for (int i = 0; i < num; ++i)
cin >> x, L.push_back(x);
for (int i = 0; i < num; ++i)
cin >> x, R.push_back(x);
while (isspace(cin.peek())) cin.ignore();
cin >> op;
result += op;
left.push_back(L);
right.push_back(R);
}
if (!solve(left, right, result))
cerr << "error\n";
else if (!res.empty())
{
auto it = find(res.begin(), res.end(), -1);
copy(res.begin(), it, ostream_iterator<int>(cout, " "));
cout << "- ";
copy(it+1, res.end(), ostream_iterator<int>(cout, " "));
cout << endl;
}
return 0;
}
|