Advertisement
cyberjab

Untitled

Sep 26th, 2024
15
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.83 KB | None | 0 0
  1. //#pragma GCC optimize("Ofast")
  2. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  3. //#define _CRT_SECURE_NO_DEPRECATE
  4. #include <iostream>
  5. #include <iomanip>
  6. #include <cstdlib>
  7. #include <cstdio>
  8. #include <string>
  9. #include <vector>
  10. #include <map>
  11. #include <set>
  12. #include <unordered_map>
  13. #include <unordered_set>
  14. #include <queue>
  15. #include <deque>
  16. #include <cmath>
  17. #include <numeric>
  18. #include <algorithm>
  19. #include <ctime>
  20. #include <chrono>
  21. #include <random>
  22. #include <functional>
  23. #include <stack>
  24. #include <fstream>
  25. //#include <windows.h>
  26. //void* operator new(size_t size) {
  27. // if (void* ptr = HeapAlloc(GetProcessHeap(), 0, size ? size : 1)) return ptr;
  28. // throw std::bad_alloc{};
  29. //}
  30. //void operator delete(void* ptr) {
  31. // HeapFree(GetProcessHeap(), 0, ptr);
  32. //}
  33.  
  34. using namespace std;
  35. using ll = long long;
  36. using db = double;
  37. using ldb = long double;
  38. using pii = pair<int, int>;
  39. using pll = pair<ll, ll>;
  40. using vint = vector<int>;
  41. using vll = vector<ll>;
  42. using vst = vector<string>;
  43. #define all(x) x.begin(), x.end()
  44. #define size(x) int(x.size())
  45. #define rep(x) for(int rep_i = 0; rep_i < x; ++rep_i)
  46. #define forp(i, s, f) for(int i = s; i < f; ++i)
  47. #define form(i, s, f) for(int i = s; i > f; --i)
  48. #define PB push_back
  49. #define MP make_pair
  50. #define F first
  51. #define S second
  52. #define elif else if
  53. #define dprint(x) for (auto now: x) cout << now << ' '
  54.  
  55. const int MOD = 1e9 + 7;
  56. const int MOD2 = 998244353;
  57. const int INF = 2e9 + 7;
  58. const ll LINF = 1e18 + 7;
  59. const double EPS = 1e-9;
  60. const long double PI = acosl(-1.0);
  61.  
  62. int n;
  63.  
  64. ifstream cinn("xml.in");
  65. ofstream coutt("xml.out");
  66.  
  67. bool check_ckob(string& s) {
  68. int cnt = 0;
  69. bool f = false;
  70. forp(i, 0, n) {
  71. if (s[i] == '<') cnt++;
  72. if (s[i] == '>') cnt--;
  73. if (cnt < 0) f = true;
  74. }
  75. if (cnt != 0) f = true;
  76. return f;
  77. }
  78.  
  79. bool check_ckob_2(string& s) {
  80. if (s[0] != '<') return false;
  81. if (s[n - 1] != '>') return false;
  82. forp(i, 1, n - 1) {
  83. if (s[i] == '>' and s[i + 1] != '<') {
  84. return false;
  85. }
  86. else if (s[i] == '/' and s[i + 1] == '/') return false;
  87. }
  88. return true;
  89. }
  90.  
  91. bool check_3(string& s) {
  92. int cnt = 0, cnt2 = 0;
  93. bool f = true;
  94. forp(i, 0, n) {
  95. //if (s[i] == '/') cnt2++;
  96. if (s[i] == '<') f = true;
  97. else if (f and s[i] == '>') {
  98. cnt++;
  99. f = false;
  100. }
  101. else if (!f and s[i] == '>') return false;
  102. }
  103. return (cnt % 2 == 0 /*and cnt2 * 2 == cnt*/);
  104. }
  105.  
  106. vst parse(string& s) {
  107. vst ret;
  108. string now;
  109. forp(i, 0, n) {
  110. if (s[i] != '<' and s[i] != '>') {
  111. now.push_back(s[i]);
  112. }
  113. else {
  114. if (!now.empty()) ret.push_back(now);
  115. now = "";
  116. }
  117. }
  118. return ret;
  119. }
  120.  
  121. bool check_idk(string a, string b) {
  122. bool f = true;
  123. int i = 0;
  124. while (i < size(a)) {
  125. if (a[i] != b[i] and f) {
  126. f = false;
  127. }
  128. else if (a[i] != b[i] and !f) {
  129. return false;
  130. }
  131. i++;
  132. }
  133. return true;
  134. }
  135.  
  136. void check_5(vst& sp) {
  137. stack<pair<string, int>> st;
  138. pii xxx = { -1, -1 };
  139. forp(i, 0, size(sp)) {
  140. if (st.empty()) {
  141. st.push({ sp[i], i });
  142. continue;
  143. }
  144. if ("/" + st.top().F == sp[i]) {
  145. st.pop();
  146. }
  147. else {
  148. st.push({sp[i], i});
  149. }
  150. }
  151. if (st.empty()) {
  152. forp(i, 0, size(sp)) {
  153. coutt << '<' << sp[i] << '>';
  154. }
  155. exit(0);
  156. }
  157. vector<pair<string, int>> xx;
  158. while (!st.empty()) {
  159. xx.push_back({ st.top() });
  160. st.pop();
  161. }
  162. /*bool f = false;
  163. forp(i, 0, n / 2 - 1) {
  164. if ("/" + xx[i].first != xx[size(xx) - 1 - i].first) {
  165. f = true;
  166. break;
  167. }
  168. }
  169. if (f) return;*/
  170. string el1 = xx[size(xx) / 2].first, el2 = xx[size(xx) / 2 - 1].first;
  171. int ind1 = xx[size(xx) / 2].S, ind2 = xx[size(xx) / 2 - 1].S;
  172. if (size(el2) - size(el1) != 1) return;
  173. // el2 and /el2 xz
  174. // el1 and /el1 xy
  175. string xy, xz;
  176. forp(i, 1, size(el2)) xz.PB(el2[i]);
  177. xy = el1;
  178. if (xz.find('/') == -1 and check_idk(el1, xz)) {
  179. sp[ind1] = xz;
  180. sp[ind2] = "/" + xz;
  181. for (auto now : sp) {
  182. coutt << '<' << now << '>';
  183. }
  184. exit(0);
  185. }
  186. if (xy.find('/') == -1 and check_idk("/" + xy, el2)) {
  187. sp[ind2] = "/" + xy;
  188. sp[ind1] = xy;
  189. for (auto now : sp) {
  190. coutt << '<' << now << '>';
  191. }
  192. exit(0);
  193. }
  194. }
  195.  
  196. void solve() {
  197. //freopen("xml.in", "r", stdin);
  198. //freopen("xml.out", "w", stdout);
  199.  
  200. string s;
  201. cinn >> s;
  202. n = size(s);
  203. vst pot;
  204. string alf = "</>";
  205. map<string, bool> sl;
  206. forp(i, 0, n) {
  207. for (auto simb : alf) {
  208. string cs = s;
  209. cs[i] = simb;
  210. bool f2 = check_ckob(cs);
  211. if (sl.count(cs)) continue;
  212. sl[cs] = f2;
  213. if (!f2) {
  214. pot.push_back(cs);
  215. }
  216. }
  217. }
  218. vst pot2;
  219. for (auto now : pot) {
  220. if (check_ckob_2(now)) pot2.push_back(now);
  221. }
  222. vst pot3;
  223. for (auto now : pot2) {
  224. if (check_3(now)) pot3.push_back(now);
  225. }
  226. //dprint(pot3);
  227. //cout << '\n';
  228. vector<vst> pot4;
  229. for (auto now : pot3) {
  230. vst x = parse(now);
  231. if (!x.empty()) pot4.push_back(x);
  232. //cout << '\n';
  233. }
  234. for (auto now : pot4) {
  235. check_5(now);
  236. }
  237. }
  238.  
  239. int main() {
  240. /*ios_base::sync_with_stdio(0);
  241. cin.tie(0);*/
  242. /*cout << setprecision(x)*/
  243. //cout << fixed;
  244. int t;
  245. t = 1;
  246. while (t > 0) {
  247. solve();
  248. t--;
  249. }
  250. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement