splot.cpp

#include <bits/stdc++.h>

using namespace std;

const int INF = 1<<20;

string s;

template<typename T1, typename T2>
inline ostream& operator<<(ostream& in, const pair<T1, T2>& x)
{
	return in<<"{"<<x.first<<", "<<x.second<<"}";
}

template<typename T1, typename T2>
inline pair<T1, T2> operator+(const pair<T1, T2>& x, const pair<T1, T2>& y)
{
	return make_pair(x.first + y.first, x.second + y.second);
}

pair<int, pair<int, pair<pair<pair<int, int>, pair<int, int>>, pair<int, int>>>> sol[1<<17];
bool full[1<<17];
bool middleLeftWhich[1<<17];
bool middleRightWhich[1<<17];
bool middleBothWhich[1<<17];

pair<int, pair<int, pair<pair<pair<int, int>, pair<int, int>>, pair<int, int>>>> solve(int i = 0)
{
	switch (s[i])
	{
		case 'o':
			return sol[i] = {i + 1, {0, {{{1, -1}, {1, -1}}, {1, -1}}}};
		case 'x':
			full[i] = true;
			return sol[i] = {i + 1, {-INF, {{{1, -1}, {1, -1}}, {1, -1}}}};
		case 'S':
		{
			auto _a = solve(i + 1);
			auto a = make_pair(_a.second.first, make_pair(make_pair(_a.second.second.first.first.first, _a.second.second.first.second.first), _a.second.second.second.first));
			auto _b = solve(_a.first);
			auto b = make_pair(_b.second.first, make_pair(make_pair(_b.second.second.first.first.first, _b.second.second.first.second.first), _b.second.second.second.first));
			assert(s[_b.first] == '#');
			full[i] = full[i + 1] || full[_a.first];
			int acost = full[i + 1] * INF, bcost = full[_a.first] * INF;
			return sol[i] = {_b.first + 1,
								{a.first + b.first,
								//left
								{{max(make_pair(a.first + b.second.first.first, 0), make_pair(a.second.first.first - bcost, 1)),
								//right
								max(make_pair(a.second.first.second + b.first, 0), make_pair(b.second.first.second - acost, 1))},
									//both double blocked
									max(make_pair(a.second.first.first + b.second.first.second, 0),
										//both single blocked
										max(make_pair(a.first + b.second.second, 1), make_pair(a.second.second + b.first, 2)))}}};
		}
		case 'P':
		{
			assert(s[i + 2] == '|');
			auto _a = solve(i + 3);
			auto a = make_pair(_a.second.first, make_pair(make_pair(_a.second.second.first.first.first, _a.second.second.first.second.first), _a.second.second.second.first));
	//			cout<<"["<<i + 3<<", "<<a.first<<"): "<<a.second<<endl;
			auto _b = solve(_a.first);
			auto b = make_pair(_b.second.first, make_pair(make_pair(_b.second.second.first.first.first, _b.second.second.first.second.first), _b.second.second.second.first));
	//			cout<<"["<<a.first<<", "<<b.first<<"): "<<b.second<<endl;
			assert(s[_b.first] == '|');
			assert(s[_b.first + 2] == '#');
			
			pair<int, int> x = {solve(i + 1).second.first, 1}, y = {solve(_b.first + 1).second.first, 1};
			
			full[i] = full[i + 3] || full[_a.first] || full[i + 1] || full[_b.first + 1];
			int acost = full[i + 3] * INF, bcost = full[_a.first] * INF, xcost = full[i + 1] * INF, ycost = full[_b.first + 1] * INF;
			
			int middleLeftUnblocked = max(a.first + b.second.first.first, a.second.first.first + b.first);
			if (middleLeftUnblocked == a.second.first.first + b.first)
				middleLeftWhich[i] = true;
			int middleLeftBlocked = a.second.first.first + b.second.first.first;
			int middleRightUnblocked = max(a.first + b.second.first.second, a.second.first.second + b.first);
			if (middleRightUnblocked == a.second.first.second + b.first)
				middleRightWhich[i] = true;
			int middleRightBlocked = a.second.first.second + b.second.first.second;
			int middleBothUnblocked = max(a.first + b.second.second, a.second.second + b.first);
			if (middleBothUnblocked == a.second.second + b.first)
				middleBothWhich[i] = true;
			int middleBothBlocked = a.second.second + b.second.second;
			
			return sol[i] = {_b.first + 3,
								//Unblocked
								{x.first + middleBothUnblocked + y.first,
								{{
									//left blocked
									//but still don't
									max(make_pair(x.first + middleBothUnblocked + y.first, 0),
										//ok do
										max(make_pair(x.second - acost - bcost - ycost, 1),
											//no x
											make_pair(x.first, 0) + max(make_pair(middleLeftBlocked - ycost, 2), make_pair(middleLeftUnblocked + y.second, 3)))),
									//right blocked
									//but still don't
									max(make_pair(x.first + middleBothUnblocked + y.first, 0),
										//ok do
										max(make_pair(y.second - acost - bcost - xcost, 1),
											//no y
											make_pair(y.first, 0) + max(make_pair(middleRightBlocked - xcost, 2), make_pair(middleRightUnblocked + x.second, 3))))},
									//both blocked
									//but still don't
									max(make_pair(x.first + middleBothUnblocked + y.first, 0),
										//ok do
										max(
											max(
												//none
												make_pair(x.first + middleBothBlocked + y.first, 1),
												//y
												make_pair(x.first + middleLeftBlocked + y.second, 2)),
											max(
												//x
												make_pair(x.second + middleRightBlocked + y.first, 3),
												//xy
												make_pair(x.second + y.second, 4))))}}};
		}
	}
	assert(false);
}

void middleLeft(int i, int a, int b);
void middleRight(int i, int a, int b);
void middleBoth(int i, int a, int b);

//int tabs;

void reconstruct(int i, int op)
{
//	++tabs;
//	cout<<string(tabs, ' ')<<i<<' '<<op<<endl;
	switch (s[i])
	{
		case 'o':
			if (op)
				s[i] = 'x';
			break;
		case 'x':
			break;
		case 'S':
			switch (op)
			{
				case 0:
					reconstruct(i + 1, 0);
					reconstruct(sol[i + 1].first, 0);
					break;
				case 1:
					switch (sol[i].second.second.first.first.second)
					{
						case 0:
							reconstruct(i + 1, 0);
							reconstruct(sol[i + 1].first, 1);
							break;
						case 1:
							reconstruct(i + 1, 1);
							break;
					}
					break;
				case 2:
					switch (sol[i].second.second.first.second.second)
					{
						case 0:
							reconstruct(i + 1, 2);
							reconstruct(sol[i + 1].first, 0);
							break;
						case 1:
							reconstruct(sol[i + 1].first, 2);
							break;
					}
					break;
				case 3:
					switch (sol[i].second.second.second.second)
					{
						case 0:
							reconstruct(i + 1, 1);
							reconstruct(sol[i + 1].first, 2);
							break;
						case 1:
							reconstruct(i + 1, 0);
							reconstruct(sol[i + 1].first, 3);
							break;
						case 2:
							reconstruct(i + 1, 3);
							reconstruct(sol[i + 1].first, 0);
							break;
					}
					break;
			}
			break;
		case 'P':
		{
			int x = i + 1, a = i + 3, b = sol[a].first, y = sol[b].first + 1;
			switch (op)
			{
				case 0:
					middleBoth(i, a, b);
					break;
				case 1:
					switch (sol[i].second.second.first.first.second)
					{
						case 0:
							middleBoth(i, a, b);
							break;
						case 1:
							s[x] = 'x';
							break;
						case 2:
							reconstruct(a, 1);
							reconstruct(b, 1);
							break;
						case 3:
							middleLeft(i, a, b);
							s[y] = 'x';
							break;
					}
					break;
				case 2:
					switch (sol[i].second.second.first.second.second)
					{
						case 0:
							middleBoth(i, a, b);
							break;
						case 1:
							s[y] = 'x';
							break;
						case 2:
							reconstruct(a, 2);
							reconstruct(b, 2);
							break;
						case 3:
							middleRight(i, a, b);
							s[x] = 'x';
							break;
					}
					break;
				case 3:
					switch (sol[i].second.second.second.second)
					{
						case 0:
							middleBoth(i, a, b);
							break;
						case 1:
							reconstruct(a, 3);
							reconstruct(b, 3);
							break;
						case 2:
							reconstruct(a, 1);
							reconstruct(b, 1);
							s[y] = 'x';
							break;
						case 3:
							reconstruct(a, 2);
							reconstruct(b, 2);
							s[x] = 'x';
							break;
						case 4:
							s[x] = s[y] = 'x';
							break;
					}
					break;
			}
			break;
		}
		default:
			assert(false);
	}
//	--tabs;
}

void middleLeft(int i, int a, int b)
{
	if (middleLeftWhich[i] == false)
	{
		reconstruct(a, 0);
		reconstruct(b, 1);
	}
	else
	{
		reconstruct(a, 1);
		reconstruct(b, 0);
	}
}

void middleRight(int i, int a, int b)
{
	if (middleRightWhich[i] == false)
	{
		reconstruct(a, 0);
		reconstruct(b, 2);
	}
	else
	{
		reconstruct(a, 2);
		reconstruct(b, 0);
	}
}

void middleBoth(int i, int a, int b)
{
	if (middleBothWhich[i] == false)
	{
		reconstruct(a, 0);
		reconstruct(b, 3);
	}
	else
	{
		reconstruct(a, 3);
		reconstruct(b, 0);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin>>s;
	
//	for (int i = 0; i < s.size(); ++i)
//		cout<<(i < 10 ? char('0' + i) : char('A' + i - 10));
//	cout<<'\n';
	
	solve();
	
//	cout<<"Whole: "<<sol[0].second<<endl;
	
	cout<<sol[0].second.second.first.first.first<<'\n';
	reconstruct(0, 1);
	cout<<s<<'\n';
}