Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#pragma GCC optimize("Ofast")
- //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- //#define _CRT_SECURE_NO_DEPRECATE
- #include <iostream>
- #include <iomanip>
- #include <cstdlib>
- #include <cstdio>
- #include <string>
- #include <vector>
- #include <map>
- #include <set>
- #include <unordered_map>
- #include <unordered_set>
- #include <queue>
- #include <deque>
- #include <cmath>
- #include <numeric>
- #include <algorithm>
- #include <ctime>
- #include <chrono>
- #include <random>
- #include <functional>
- #include <stack>
- #include <fstream>
- //#include <windows.h>
- //void* operator new(size_t size) {
- // if (void* ptr = HeapAlloc(GetProcessHeap(), 0, size ? size : 1)) return ptr;
- // throw std::bad_alloc{};
- //}
- //void operator delete(void* ptr) {
- // HeapFree(GetProcessHeap(), 0, ptr);
- //}
- using namespace std;
- using ll = long long;
- using db = double;
- using ldb = long double;
- using pii = pair<int, int>;
- using pll = pair<ll, ll>;
- using vint = vector<int>;
- using vll = vector<ll>;
- using vst = vector<string>;
- #define all(x) x.begin(), x.end()
- #define size(x) int(x.size())
- #define rep(x) for(int rep_i = 0; rep_i < x; ++rep_i)
- #define forp(i, s, f) for(int i = s; i < f; ++i)
- #define form(i, s, f) for(int i = s; i > f; --i)
- #define PB push_back
- #define MP make_pair
- #define F first
- #define S second
- #define elif else if
- #define dprint(x) for (auto now: x) cout << now << ' '
- const int MOD = 1e9 + 7;
- const int MOD2 = 998244353;
- const int INF = 2e9 + 7;
- const ll LINF = 1e18 + 7;
- const double EPS = 1e-9;
- const long double PI = acosl(-1.0);
- int n;
- ifstream cinn("xml.in");
- ofstream coutt("xml.out");
- bool check_ckob(string& s) {
- int cnt = 0;
- bool f = false;
- forp(i, 0, n) {
- if (s[i] == '<') cnt++;
- if (s[i] == '>') cnt--;
- if (cnt < 0) f = true;
- }
- if (cnt != 0) f = true;
- return f;
- }
- bool check_ckob_2(string& s) {
- if (s[0] != '<') return false;
- if (s[n - 1] != '>') return false;
- forp(i, 1, n - 1) {
- if (s[i] == '>' and s[i + 1] != '<') {
- return false;
- }
- else if (s[i] == '/' and s[i + 1] == '/') return false;
- }
- return true;
- }
- bool check_3(string& s) {
- int cnt = 0, cnt2 = 0;
- bool f = true;
- forp(i, 0, n) {
- //if (s[i] == '/') cnt2++;
- if (s[i] == '<') f = true;
- else if (f and s[i] == '>') {
- cnt++;
- f = false;
- }
- else if (!f and s[i] == '>') return false;
- }
- return (cnt % 2 == 0 /*and cnt2 * 2 == cnt*/);
- }
- vst parse(string& s) {
- vst ret;
- string now;
- forp(i, 0, n) {
- if (s[i] != '<' and s[i] != '>') {
- now.push_back(s[i]);
- }
- else {
- if (!now.empty()) ret.push_back(now);
- now = "";
- }
- }
- return ret;
- }
- bool check_idk(string a, string b) {
- bool f = true;
- int i = 0;
- while (i < size(a)) {
- if (a[i] != b[i] and f) {
- f = false;
- }
- else if (a[i] != b[i] and !f) {
- return false;
- }
- i++;
- }
- return true;
- }
- void check_5(vst& sp) {
- stack<pair<string, int>> st;
- pii xxx = { -1, -1 };
- forp(i, 0, size(sp)) {
- if (st.empty()) {
- st.push({ sp[i], i });
- continue;
- }
- if ("/" + st.top().F == sp[i]) {
- st.pop();
- }
- else {
- st.push({sp[i], i});
- }
- }
- if (st.empty()) {
- forp(i, 0, size(sp)) {
- coutt << '<' << sp[i] << '>';
- }
- exit(0);
- }
- vector<pair<string, int>> xx;
- while (!st.empty()) {
- xx.push_back({ st.top() });
- st.pop();
- }
- /*bool f = false;
- forp(i, 0, n / 2 - 1) {
- if ("/" + xx[i].first != xx[size(xx) - 1 - i].first) {
- f = true;
- break;
- }
- }
- if (f) return;*/
- string el1 = xx[size(xx) / 2].first, el2 = xx[size(xx) / 2 - 1].first;
- int ind1 = xx[size(xx) / 2].S, ind2 = xx[size(xx) / 2 - 1].S;
- if (size(el2) - size(el1) != 1) return;
- // el2 and /el2 xz
- // el1 and /el1 xy
- string xy, xz;
- forp(i, 1, size(el2)) xz.PB(el2[i]);
- xy = el1;
- if (xz.find('/') == -1 and check_idk(el1, xz)) {
- sp[ind1] = xz;
- sp[ind2] = "/" + xz;
- for (auto now : sp) {
- coutt << '<' << now << '>';
- }
- exit(0);
- }
- if (xy.find('/') == -1 and check_idk("/" + xy, el2)) {
- sp[ind2] = "/" + xy;
- sp[ind1] = xy;
- for (auto now : sp) {
- coutt << '<' << now << '>';
- }
- exit(0);
- }
- }
- void solve() {
- //freopen("xml.in", "r", stdin);
- //freopen("xml.out", "w", stdout);
- string s;
- cinn >> s;
- n = size(s);
- vst pot;
- string alf = "</>";
- map<string, bool> sl;
- forp(i, 0, n) {
- for (auto simb : alf) {
- string cs = s;
- cs[i] = simb;
- bool f2 = check_ckob(cs);
- if (sl.count(cs)) continue;
- sl[cs] = f2;
- if (!f2) {
- pot.push_back(cs);
- }
- }
- }
- vst pot2;
- for (auto now : pot) {
- if (check_ckob_2(now)) pot2.push_back(now);
- }
- vst pot3;
- for (auto now : pot2) {
- if (check_3(now)) pot3.push_back(now);
- }
- //dprint(pot3);
- //cout << '\n';
- vector<vst> pot4;
- for (auto now : pot3) {
- vst x = parse(now);
- if (!x.empty()) pot4.push_back(x);
- //cout << '\n';
- }
- for (auto now : pot4) {
- check_5(now);
- }
- }
- int main() {
- /*ios_base::sync_with_stdio(0);
- cin.tie(0);*/
- /*cout << setprecision(x)*/
- //cout << fixed;
- int t;
- t = 1;
- while (t > 0) {
- solve();
- t--;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement